看题解时全程:wow
题意:给出n个数,将其按顺序分为k组,令每组的价值为该组不同的数的个数。求一种分法,使得所有组价值和最大。
解:设dp[i][j]为将前 j 个数分为 i 组时的最大价值,显然有dp[i][j]=max(dp[i-1][k]+sum[k+1...j]),sum[k+1...j]为[k+1...j]中不同数的个数。然后优化求解过程,先解决sum怎么求。设原数组为a[i],令c[i]为区间[i, n]内不同数的个数,pre[i]为a[i]最后一次出现的位置,那么对于每一个i,c[pre[i]+1...i]+1,最终结果即为数组定义。意思是在pre[i]+1到i之间没有出现过a[i],那么它可以对答案贡献1,并且这样做不会有重复加的情况出现。
以样例3为例:
a: 7 7 8 7 7 8 1 7
pre+1:1 2 1 3 5 4 1 6
index: 1 2 3 4 5 6 7 8
c: 3 3 3 3 3 3 2 1
然后再来看这道题。通常我们先枚举i,再枚举j,也就是一个数一个数往里加。每添加一个数j,就可以获得所有的[k+1...j],很快乐,直接在dp[i-1]上加然后求最大值即可。区间加和求最大值的数据结构显然用线段树。注意给dp[i][k]加上c[k+1]的值,不是c[k]。
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define maxx 35005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 2520 int a[maxx]={0}; int dp[55][maxx]={0}; int pre[maxx]={0},pos[maxx]={0}; struct node{ int val,lazy; }tr[maxx*4]; void pushup(int now){ tr[now].val=max(tr[now*2].val,tr[now*2+1].val); } void pushdown(int now){ if(!tr[now].lazy){ return; } tr[now*2].lazy+=tr[now].lazy; tr[now*2+1].lazy+=tr[now].lazy; tr[now*2].val+=tr[now].lazy; tr[now*2+1].val+=tr[now].lazy; tr[now].lazy=0; } int ii; void build(int now,int l,int r){ if(l==r){ tr[now].val=dp[ii][l-1]; tr[now].lazy=0; return ; } tr[now].lazy=0; int mid=(l+r)/2; build(now*2,l,mid); build(now*2+1,mid+1,r); pushup(now); } void add(int now,int l,int r,int s,int e){ if(s<=l&&r<=e){ tr[now].val+=1; tr[now].lazy+=1; return; } pushdown(now); int mid=(l+r)/2; if(s<=mid) add(now*2,l,mid,s,e); if(mid<e) add(now*2+1,mid+1,r,s,e); pushup(now); } int query(int now,int l,int r,int s,int e){ if(s<=l&&r<=e){ return tr[now].val; } pushdown(now); int mid=(l+r)/2; int res=0; if(s<=mid) res=max(res, query(now*2,l,mid,s,e)); if(mid<e) res=max(res, query(now*2+1,mid+1,r,s,e)); return res; } signed main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ pre[i]=pos[a[i]]+1; pos[a[i]]=i; } for(int i=1;i<=k;i++){ ii=i-1; build(1,1,n); for(int j=1;j<=n;j++){ add(1,1,n,pre[j],j); dp[i][j]= query(1,1,n,1,j); } } printf("%d\n",dp[k][n]); return 0; } //dp[i][j] the first j th num, distribute into i blocks //dp[i][j]=max(dp[i-1][k]+sum[k+1...j])View Code
标签:833B,lazy,val,int,tr,CodeForces,Bakery,now,dp From: https://www.cnblogs.com/capterlliar/p/16912969.html