首页 > 其他分享 >CF573D Bear and Cavalry

CF573D Bear and Cavalry

时间:2024-11-02 09:19:41浏览次数:1  
标签:Cavalry dh CF573D idw Bear rd 1ll idh INF

原题链接

比较简单的 \(\text{dp}\) 题。

看见题目的 \(\sum w_ih_i\) 式子,很容易想到排序不等式,所以我们先对 \(w,h\) 排序,然后分情况讨论。

  • 若 \(w_i,h_i\) 对应的编号不相等,肯定是把它们配对。

  • 若 \(w_i,h_i\) 对应的编号相等,考虑这样的连法:

  • 若是这种情况也不合法,或者它们之后又有一个点不合法,我们再加一个点,会得到两种情况:

而这样一定可以得到最优,之后不合法的规模继续扩大,我们也可以拆分成上述的小问题。

所以转移方程易得:\(f_i=\max\begin{cases} f_{i-1}+w_ih_i \\f_{i-2}+w_ih_{i-1}+w_{i-1}h_i \\f_{i-3}+w_ih_{i-1}+w_{i-1}h_{i-2}+w_{i-2}h_i \\f_{i-3}+w_ih_{i-2}+w_{i-1}h_{i}+w_{i-2}h_{i-1} \end{cases}\)

从大往小进行转移,转移前注意判断是否合法,时间复杂度 \(O(nq)\),卡卡常似乎能过。

但是这个方程明显支持矩阵优化,我们列出转移矩阵,用线段树维护即可。

我们用广义矩阵乘法:\(C_{i,j}=\max_{k=1}^{m}A_{i,k}+B_{k,j}\),然后列出式子:

\(\begin{bmatrix} f_{i-1} \\f_{i-2} \\f_{i-3} \end{bmatrix}\times \begin{bmatrix} w_ih_i& w_{i}h_{i-1}+w_{i-1}h_i&\max\{式子太长懒得写\} \\ 0& -\text{INF} &-\text{INF} \\ -\text{INF}& 0 &-\text{INF} \end{bmatrix}=\begin{bmatrix} f_{i}\\f_{i-1}\\f_{i-2} \end{bmatrix}\)

注意线段树 \(\text{pushup}\) 时的顺序,我们的转移是从大往小做的。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define in inline
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=1e5+10;
const ll INF=1e17;
int n,q,w[N],h[N],idw[N],idh[N],dw[N],dh[N],tmp[N];
bool cmp(int a,int b){return tmp[a]<tmp[b];}
struct matrix{
	ll a[3][3];
	matrix(){memset(a,0,sizeof(a));}
	matrix operator*(matrix const&T){
		matrix res;
		FOR(i,0,2) FOR(j,0,2) res.a[i][j]=-INF;
		FOR(i,0,2){
			FOR(k,0,2){
				ll r=a[i][k];
				FOR(j,0,2) res.a[i][j]=max(res.a[i][j],r+T.a[k][j]);
			}
		}
		return res;
	}
}g[N],tr[N<<2];
void pushup(int u){tr[u]=tr[u<<1|1]*tr[u<<1];}
void build(int u,int l,int r){
	if(l==r){tr[u]=g[l];return;}
	int mid=(l+r)>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int l,int r,int x){
	if(l==r){tr[u]=g[l];return;}
	int mid=(l+r)>>1;
	if(x<=mid) modify(u<<1,l,mid,x);
	else modify(u<<1|1,mid+1,r,x);
	pushup(u);
}
void init(int x){
	if(idw[x]!=idh[x]) g[x].a[0][0]=1ll*w[x]*h[x];
	else g[x].a[0][0]=-INF;
	if(x>1) g[x].a[0][1]=(idw[x]!=idh[x-1]&&idw[x-1]!=idh[x])?1ll*w[x]*h[x-1]+1ll*w[x-1]*h[x]:-INF;
	else g[x].a[0][1]=-INF;
	if(x>2){
		bool flag=false;ll res=-INF;
		if(idw[x]!=idh[x-1]&&idw[x-1]!=idh[x-2]&&idw[x-2]!=idh[x])
			flag=true,res=max(res,1ll*w[x]*h[x-1]+1ll*w[x-1]*h[x-2]+1ll*w[x-2]*h[x]);
		if(idw[x]!=idh[x-2]&&idw[x-1]!=idh[x]&&idw[x-2]!=idh[x-1])
			flag=true,res=max(res,1ll*w[x]*h[x-2]+1ll*w[x-1]*h[x]+1ll*w[x-2]*h[x-1]);
		g[x].a[0][2]=res;
	}
	else g[x].a[0][2]=-INF;
	g[x].a[1][0]=g[x].a[2][1]=0,g[x].a[1][1]=g[x].a[1][2]=g[x].a[2][0]=g[x].a[2][2]=-INF;
}
int main(){
	n=rd,q=rd;
	FOR(i,1,n) w[i]=rd,idw[i]=i,tmp[i]=w[i];
	sort(idw+1,idw+1+n,cmp);
	FOR(i,1,n) w[i]=tmp[idw[i]];
	FOR(i,1,n) h[i]=rd,idh[i]=i,tmp[i]=h[i];
	sort(idh+1,idh+1+n,cmp);
	FOR(i,1,n) h[i]=tmp[idh[i]];
	FOR(i,1,n) dw[idw[i]]=i,dh[idh[i]]=i;
	FOR(i,1,n) init(i);
	build(1,1,n);
	while(q--){
		int x=rd,y=rd;
		swap(dh[x],dh[y]),swap(idh[dh[x]],idh[dh[y]]);
		FOR(i,dh[x],min(n,dh[x]+2)) init(i),modify(1,1,n,i);
		FOR(i,dh[y],min(n,dh[y]+2)) init(i),modify(1,1,n,i);
		printf("%lld\n",tr[1].a[0][0]);
	}
	return 0;
}

标签:Cavalry,dh,CF573D,idw,Bear,rd,1ll,idh,INF
From: https://www.cnblogs.com/summ1t/p/18521628

相关文章

  • 深入解析:JWT Bearer 认证在 .NET Core 中的应用
    在现代Web应用中,安全认证是确保用户数据和系统安全的重要一环。JSONWebToken(JWT)是一种流行的认证方式,它可以在客户端和服务端之间安全地传递信息。本文将详细介绍JWTBearer认证的概念、工作原理、在.NETCore中的实现步骤,以及最佳实践。一、什么是JWT?JSONWebTok......
  • CF771A. Bear and Friendship Condition 题解 并查集
    题目链接:https://codeforces.com/problemset/problem/771/A视频讲解:https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6题目大意:判断一个无向图中的每个连通块是否都是一个完全图。首先我们可以用并查集维护每个连通块的大小。其次,我们可以开一个\(cnt_i\)表示以节点\(i\)......
  • 题解:CF573D Bear and Cavalry
    因为这是远古题目,所以根据现在的评测机速度,用\(O(nq)\)的做法也是可以过的。也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种\(O(n)\)的算法求解答案。这道题类似资源分配型动态规划,所以我们可以设\(dp_i\)表示分配前\(i\)个人的答案。直接写是不行的,我......
  • CF573E Bear and Bowling 题解
    Description给定一个长度为\(n\)的序列\(a_{1\dotsn}\)。你要求一个\(a\)的子序列\(b_{1\dotsm}\)(可以为空),使得\(\sum_{i=1}^mib_i\)的值最大。\(n\le10^5\),\(|a_i|\le10^7\)。Solution有一个显然的dp是设\(f_{i,j}\)表示前\(i\)个数,选\(j\)个数的......
  • 使用django-treebeard实现树类型存储与编辑
    前言其实之前做很多项目都有遇到跟树相关的功能,以前都是自己实现的,然后前端很多UI组件库都有Tree组件,套上去就可以用。不过既然用Django了,还是得充分发挥一下生态的优势,但是我找了半天,也就这个treebeard能用,其他要不停更了要不就功能很拉,没有可视化编辑树的功能。难道Djang......
  • 题解:CF771A Bear and Friendship Condition
    CF771ABearandFriendshipCondition题解算法并查集,图的基本性质分析题目意思是,一旦有一些点联通,那么这些点必须两两直接相连。换句话讲,就是图中的每个联通块都是完全图。所谓完全图,就是图中的每个点都两两相连,假设一个完全图有\(n\)个点,那么我们可以通过乘法原理算出这......
  • A. Bear and Prime 100
    原题链接题解1.如果是一百以内的合数,那么一定可以由两个不大于50的质数组成2.交互题关键就在于询问和返回的结果cout<<''';fflush(stdout);cin>>...code#include<bits/stdc++.h>usingnamespacestd;boolcheck(intx){for(inti=2;i*i<=x;i++){i......
  • Bear and String Distance
    传送锚点:codeforces.comCopy426bearoutputroarinput27afoutputdbinput31000heyoutput-1思路此题答案不限有点类似贪心,每一步都要做到最佳,将k不断变小code#include<iostream>#include<vector>#include<algorithm>#include<cstring>usingnamesp......
  • CF628F Bear and Fair Set
    传送门网络流好题。先将所有限制按\(u_i\)排序,同时令\(u_0=0,t_0=0\)和\(u_{q+1}=b,t_{q+1}=n\)。(下面就把\(q\leftarrowq+1\)了)这些限制会把\(1\simb\)分成\(q\)段。先检查一遍,如果出现\(u_i\)更大反而\(t_i\)更小,unfair;如果出现一个段内数的个数爆了,unfair......
  • CF771C Bear and Tree Jumps
    题目大意:给定一棵有\(n\)个节点的树,要你统计\(\sum_{1\lex\ley\len}{dist(x,y)/k}\)(\(dist(x,y)\)表示\(x\)到\(y\)的距离)\(n\le2\times10^5,k\le5\)解法:一道换根\(dp\)套路题。首先看到树上统计问题,考虑树形\(dp\),那么我们设\(g(u)\)为以\(......