贪心找性质+dp表示+矩阵表示+线段树维护:CF573D

这篇具有很好参考价值的文章主要介绍了贪心找性质+dp表示+矩阵表示+线段树维护:CF573D。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

比较套路的题目

首先肯定贪心一波,两个都排序后尽量相连。我一开始猜最多跨1,但其实最多跨2,考虑3个人的情况:

贪心找性质+dp表示+矩阵表示+线段树维护:CF573D,矩阵,线性代数,贪心,线段树,dp,dp优化

我们发现第3个人没了,所以可以出现跨2的情况

然后直接上dp,由 i − 1 , i − 2 , i − 3 i-1,i-2,i-3 i1,i2,i3 转移过来。

然后这显然可以拿矩阵表示。

然后显然可以拿线段树维护。

后面三部分都是比较套路的。文章来源地址https://www.toymoban.com/news/detail-723963.html

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 30010
int n, m, i, j, k, T;
int a[N], b[N], ia[N], ib[N], shu[N], pos[N], x, y, q, rt; 

int Not(int x, int y) { if(shu[ia[x]]!=ib[y]) return 1; return 0; }

struct Martix {
	int c[3][3]; 
	void mem() { memset(c, 0, sizeof(c)); }
	void init() { mem(); c[0][0]=c[1][1]=c[2][2]=1; }
	void min() { c[0][0]=c[0][1]=c[0][2]=c[1][0]=c[1][1]=c[1][2]=c[2][1]=c[2][2]=c[2][0]=-1e15;  }
	Martix operator *(const Martix A) const { //max+
		Martix B; B.min(); 
		for(int i=0; i<3; ++i) 
			for(int j=0; j<3; ++j) 
				for(int k=0; k<3; ++k)  
					B.c[i][j]=max(B.c[i][j], c[i][k]+A.c[k][j]); 
		return B; 
	}
	void make(int x) {//生成在x位置的矩阵 
		min(); c[1][0]=c[2][1]=0; 
		if(Not(x, x)) c[0][0]=a[x]*b[x]; 
//		if(x==1) return printf("# 1 : \n"), (*this).print(), void(); 
		if(x==1) return ; 
		if(Not(x, x-1) && Not(x-1, x)) c[0][1]=a[x]*b[x-1]+a[x-1]*b[x]; 
//		if(x==2) return printf("# 2: \n"), (*this).print(), void(); 
		if(x==2) return ; 
		if(Not(x, x-1) && Not(x-1, x-2) && Not(x-2, x)) c[0][2]=max(c[0][2], a[x]*b[x-1]+a[x-1]*b[x-2]+a[x-2]*b[x]); 
		if(Not(x, x-2) && Not(x-1, x) && Not(x-2, x-1)) c[0][2]=max(c[0][2], a[x]*b[x-2]+a[x-1]*b[x]+a[x-2]*b[x-1]); 
		if(Not(x, x-2) && Not(x-1, x-1) && Not(x-2, x)) c[0][2]=max(c[0][2], a[x]*b[x-2]+a[x-1]*b[x-1]+a[x-2]*b[x]); 
//		printf("# %lld : \n", x); (*this).print(); 
	}
	int que() {
//		printf("RT : "); 
//		(*this).print(); 
		Martix B; B.min(); B.c[0][0]=0; 
		B=(*this)*B; return B.c[0][0]; 
	}
	void print() {
		printf("---\n"); 
		for(int i=0; i<3; ++i, printf("\n")) 
			for(int j=0; j<3; ++j) printf("%lld ", c[i][j]); 
		printf("\n"); 
	}
};

struct Segment_tree {
	int tot, ls[N<<2], rs[N<<2]; 
	Martix s[N<<2]; 
	void push_up(int k) { s[k]=s[rs[k]]*s[ls[k]]; }   //注意乘法顺序 
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) return s[k].make(l), void(); 
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); build(rs[k], mid+1, r); 
		push_up(k); 
	}
	void modify(int k, int l, int r, int x) {
		if(l==r) return s[k].make(x), void(); 
		int mid=(l+r)>>1; 
		if(x<=mid) modify(ls[k], l, mid, x); 
		else modify(rs[k], mid+1, r, x); 
		push_up(k); 
//		printf("[%lld %lld] : \n", l, r); s[k].print(); 
	}
}Seg;

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	for(i=1; i<=n; ++i) a[i]=read(), ia[i]=i, shu[i]=i; //shu:第i个人马的编号 
	for(i=1; i<=n; ++i) b[i]=read(), ib[i]=i; 
	sort(ia+1, ia+n+1, [] (int x, int y) { return a[x]>a[y]; }); 
	sort(ib+1, ib+n+1, [] (int x, int y) { return b[x]>b[y]; }); 
	sort(a+1, a+n+1); reverse(a+1, a+n+1); //按实力排好,则原顺序已经没必要了 
	sort(b+1, b+n+1); reverse(b+1, b+n+1); 
//	cout<<"ia : "; for(i=1; i<=n; ++i) printf("%lld ", ia[i]); puts(""); 
//	cout<<"ib : "; for(i=1; i<=n; ++i) printf("%lld ", ib[i]); puts(""); 
//	cout<<"a : "; for(i=1; i<=n; ++i) printf("%lld ", a[i]); puts(""); 
//	cout<<"b : "; for(i=1; i<=n; ++i) printf("%lld ", b[i]); puts(""); 
	//ia, ib排序后排名第i对应的原编号 
	for(i=1; i<=n; ++i) pos[ia[i]]=i; //某编号对应的排名 
//	cout<<"pos : "; for(i=1; i<=n; ++i) printf("%lld ", pos[i]); puts(""); 

	Seg.build(rt, 1, n); 
	while(q--) {
		x=read(); y=read(); swap(shu[x], shu[y]);  //交换了马
//		cout<<"shu : "; for(i=1; i<=n; ++i) printf("%lld ", shu[i]); puts(""); 
		for(i=max(1ll, pos[x]-3); i<=min(n, pos[x]+3); ++i) Seg.modify(1, 1, n, i); 
		for(i=max(1ll, pos[y]-3); i<=min(n, pos[y]+3); ++i) Seg.modify(1, 1, n, i); 
		printf("%lld\n", Seg.s[1].que()); 
	}
	return 0;
}

到了这里,关于贪心找性质+dp表示+矩阵表示+线段树维护:CF573D的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

    D e s c r i p t i o n mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下: 1 u v w 表示从 u u u 向 v v v 连接 1 1 1 条长度为 w w w 的有向边 2 u l r w 表示从 u u u 向 i i i ( i ∈ [ l , r ] iin [l,r] i ∈ [ l , r ] )连接 1 1 1 条长度为 w w w

    2024年02月20日
    浏览(89)
  • 【二分+贪心】CF1665 C

    Problem - C - Codeforces 题意:   思路: 一开始想太简单wa6了 只想到先感染大的分量,然后最后把最大的分量剩下的染色 但是可能会有别的分量更大(因为最后给最大的染色之后可能不再是最大的) 可以用堆维护,但是这里用二分做法 我们可以二分答案 mid ,问题就变成了 mid 秒

    2024年02月13日
    浏览(38)
  • 【DP】CF Edu 21 E

    Problem - E - Codeforces 题意: 思路: 就是一个 N为1e5,M为3e5的背包问题,不过特殊条件是 w = 3 我们去从最简单的情况开始考虑 当只有w = 1的物品和w = 2的物品时,考虑贪心地把物品按价值排序,然后选 这个非常的正确,然后加上w = 3的直接枚举即可 对于小数据的DP,我们可以尝

    2024年02月10日
    浏览(34)
  • CF1881F Minimum Maximum Distance 题解 贪心+DFS

    You have a tree with n n n vertices, some of which are marked. A tree is a connected undirected graph without cycles. Let f i f_i f i ​ denote the maximum distance from vertex i i i to any of the marked vertices. Your task is to find the minimum value of f i f_i f i ​ among all vertices. For example, in the tree shown in the example, vertices 2 2 2 , 6 6

    2024年02月22日
    浏览(42)
  • Codeforces Round 916 (Div. 3)(E:贪心 F贪心dfs G tarjan+topsort +线段树优化建图)

    A:直接暴力统计每个字符的次数是否达标即可 B:直接先输出所需要的k,然后降序输出剩下的即可 C: 直接枚举最后操作到哪个位置就行了,然后贪心一直操作1到i的位置的b最大值即可 D: 先固定第一次是A 第二次是B 第三次是C 枚举B为中介点i,然后求1到i-1的A的最大值,和

    2024年01月17日
    浏览(41)
  • Codeforces Round 768 (Div. 1) D. Flipping Range(思维题 等价类性质 dp)

    题目 思路来源 官方题解 洛谷题解 题解 可操作的最短区间长度肯定是gcd,记为g,然后考虑如何dp 考虑g个等价类,每个等价类i,i+g,i+2*g,... 每次翻转长度为g的区间,会同时影响到g个等价类总的翻转的奇偶性, 性质一:只有每个等价类翻的次数奇偶性相同才合法  性质二:此

    2024年01月19日
    浏览(35)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(94)
  • 【DP】【贪心】122.买卖股票的最佳时机II

    题目 六种股票问题总结https://blog.csdn.net/weixin_47692079/article/details/117202705

    2024年01月19日
    浏览(40)
  • 力扣hot100 最长递增子序列 线性DP 贪心 二分

    Problem: 300. 最长递增子序列 时间复杂度: O ( n 2 ) O(n^2) O ( n 2 ) 空间复杂度: O ( n ) O(n) O ( n ) 👨‍🏫 参考题解 时间复杂度: O ( n log ⁡ n ) O(nlog{n}) O ( n lo g n ) 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月20日
    浏览(41)
  • 矩阵的秩的性质

    前置知识: 行列式的性质 逆矩阵的性质 【定义】矩阵的秩 线性方程组与矩阵的秩 矩阵初等变换与矩阵乘法的联系 前置定义 2 设在矩阵 A boldsymbol{A} A 中有一个不等于 0 0 0 的 r r r 阶子式 D D D ,且所有 r + 1 r+1 r + 1 阶子式(如果存在的话)全等于 0 0 0 ,那么 D D D 称为矩阵

    2023年04月08日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包