题面

题意

给你n个数，将它们分成k组（不改变顺序），每组的价值为这组中数字的种数，求所有组的最大价值和。

做法

首先思考最朴素的dp： dp[i][j]表示将前i个数分成j组的最大价值和。 因此，dp[i][j]=max(dp[i-k][j-1]+val[i-k+1][i]). 时间复杂度为O(k*n^2). 考虑优化这个dp，可以先求出dp[i][1]（这列数的前缀的价值），然后求出dp[i][2],dp[i][3]……dp[i][k]，具体求dp[i][j]值的时候，可以将dp[i][j-1]的值存入线段树，逐个数考虑其贡献，发现每个数对答案做出的贡献可以转化为区间加，每次求出最大值即可。

代码

#include<iostream> #include<cstdio> #define mid ((l+r)>>1) #define N 35010 using namespace std; int n,k,num[N],last[N],pos[N],dp[N][60],tt=1,tmp; struct Node { int ls,rs,mx,sum; } node[N<<1]; void build(int now,int l,int r) { if(l==r) return; if(l<=mid) { node[now].ls=++tt; build(tt,l,mid); } if(mid<r) { node[now].rs=++tt; build(tt,mid+1,r); } } void add(int now,int l,int r,int u,int v,int w) { if(l==u&&v==r) { node[now].sum+=w; return; } if(u<=mid) { add(node[now].ls,l,mid,u,min(mid,v),w); } if(mid<v) { add(node[now].rs,mid+1,r,max(mid+1,u),v,w); } node[now].mx=max(node[node[now].ls].mx+node[node[now].ls].sum,node[node[now].rs].mx+node[node[now].rs].sum); } void ql(int now,int l,int r,int u) { node[now].sum=node[now].mx=0; if(l==r) return; if(l<=mid) { ql(node[now].ls,l,mid,u); } if(mid<r) { ql(node[now].rs,mid+1,r,u); } } void chg(int now,int l,int r,int u,int v) { if(l==r) { node[now].mx=v; return; } int res=0; if(u<=mid) { chg(node[now].ls,l,mid,u,v); } else { chg(node[now].rs,mid+1,r,u,v); } node[now].mx=max(node[node[now].ls].mx+node[node[now].ls].sum,node[node[now].rs].mx+node[node[now].rs].sum); } int main() { int i,j; cin>>n>>k; for(i=1; i<=n; i++) { scanf("%d",&num[i]); if(!pos[num[i]]) tmp++; last[i]=pos[num[i]]; pos[num[i]]=i; dp[i][1]=tmp; } build(1,1,n); for(i=2; i<=k; i++) { ql(1,1,n,i-1); for(j=1;j<i;j++) chg(1,1,n,j,dp[j][i-1]); for(j=i; j<=n; j++) { add(1,1,n,max(i-1,last[j]),j-1,1); dp[j][i]=node[1].mx+node[1].sum; chg(1,1,n,j,dp[j][i-1]); } } cout<<dp[n][k]; }