csp2024T3

题目大意：对于每个数而言，可以将其染成红或蓝，对于每一个数，定义其贡献为 $ai$ ，当且仅当这个数最近的同色数与其相等，否则其贡献为0，求最大贡献和。

思路：考虑dp

1.考场20多分钟想的奇怪东西：

定义 $f[n][0/1]$ 表示第i为的颜色为蓝或红，则有转移： $f[i][0]=f[j][0]+(a[i]==a[j])*a[i]+calc(j+1,i-1,1)$

$f[i][1]=f[j][1]+(a[i]==a[j])*a[i]+calc(j+1,i-1,0)$

问题出在calc中，当时想的是 $sum=\sum_{st}^{ed}f[i][cl]$ 就是他的值。但其实拿那个样例比对一下，就能发现 $sum=f[st][cl]+sum_{st+1}^{ed}(a[i]==a[i-1])*a[i]$ ，对于最左边的数，它的贡献是 $f[st][cl]$ ，其他点就是把相邻两个数的值相等的贡献加起来。注意到如果相邻两个相同数被染成同样的颜色，那么应该是 $f[st-1][cl]$ （一定要拿特殊数据测一测，否则只有5pts）。

2. $O(n^2)$ 呼之欲出，维护前缀和 $q[i]$ 表示前i位的calc值，那么 $calc(j+1,i-1)=q[i-1]-q[j+1+1-1]=q[i-1]-q[j+1]$

$q[i]=a[i]*(a[i]==a[i-1])$

$q[i]+=q[i-1]$

#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int f[N],n,a[N],ans;int calc(int st,int ed){int ans=f[st];if(st>ed&&st-1>=1)  return f[st-1];if(st==ed)  return f[st];for(int i=st+1;i<=ed;i++)  ans+=(a[i]==a[i-1])*a[i]; return ans;
}
void solve(){memset(f,0,sizeof f);cin>>n;for(int i=1;i<=n;i++)  cin>>a[i];for(int i=2;i<=n;i++){f[i]=f[i-1];int sum=0;for(int j=i-1;j>=1;j--){//if(a[i]!=a[j])  continue;int st=j+1,ed=i-1;//st+1 - edif(st>ed&&st-1>=1)  f[i]=max(f[i],(a[i]==a[j])*a[i]+f[st-1]);else if(st==ed)  f[i]=max(f[i],(a[i]==a[j])*a[i]+f[st]);else if(st<ed){sum+=(a[j+2]==a[j+1])*a[j+1];f[i]=max(f[i],(a[i]==a[j])*a[i]+sum+f[st]);} //f[i]=max(f[i],(a[i]==a[j])*a[i]+calc(j+1,i-1));}}cout<<f[n]<<endl;
}
int main(){int T;cin>>T;while(T--)  solve();return 0;
}

考虑优化：很明显只有相等的值才能造成贡献

策略1.两位相邻， $f[i]=max(f[i],(a[i]==a[i-1])*a[i]+f[i-1]);$

策略2.两位之间差一位， $f[i]=max(f[i],(a[i]==a[i-2])*a[i]+f[i-1]);$

策略3.两位之间的格子超过两位， $f[i]=max(f[i],a[i]+q[i-1]-q[t+1]+f[t+1]);$

其中t表示其中与其相同值的格子的位置。

直接分类是接近 $O(n^2)$ ，考虑 $-q[t+1]+f[t+1]$ 的单调性，可以知道这是单调递增的，每次以上次最后点为起点， $t>i-3$ 是为下一个点的起点和这个点的终点即可。

复杂度 $O(n)$ ，当然没看出单调性也可以套个线段树维护后面那个东西，本题不卡常。

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 1e6 + 10;int f[N],n,a[N],ans,q[N],mx,g[N],maxn,lst[N];
vector<int> v[N];
void solve(){memset(f,0,sizeof f);memset(q,0,sizeof q);maxn=0;memset(g,0,sizeof g);memset(lst,0,sizeof lst); cin>>n;for(int i=1;i<=n;i++){cin>>a[i];maxn=max(maxn,a[i]);if(a[i]==a[i-1])  q[i]=a[i];q[i]+=q[i-1];v[a[i]].push_back(i);}  for(int i=2;i<=n;i++){f[i]=f[i-1];int sum=0;f[i]=max(f[i],(a[i]==a[i-1])*a[i]+f[i-1]);if(i>2)  f[i]=max(f[i],(a[i]==a[i-2])*a[i]+f[i-1]);for(int j=lst[a[i]];j<v[a[i]].size();j++){int t=v[a[i]][j];if(t>i-3){lst[a[i]]=j;break;}  f[i]=max(f[i],a[i]+q[i-1]-q[t+1]+f[t+1]);}}cout<<f[n]<<endl;for(int i=1;i<=maxn;i++)  v[i].clear();
}
signed main(){int T;cin>>T;while(T--)  solve();return 0;
}

summary：自己的t2很蒙，搞到t3只有1个小时多一点，实际想这一题只有30-40分钟，没有自己仔细调一调，导致暴力dp都没有写出来。希望noip能自己写出一个正解dp出来

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/3598.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！