题目链接

codeforces 833B. The Bakery

分析

这道题的dp方程不难，关键在于如何优化dp状态转移

dp[i][j]=max1≤x≤j(dp[i−1][x]+c(x+1,j))

dp[i][j] 表示 i 个盒子装 1−j 的时候的最优值

c(i,j) 表示 i−j 的不同值的数目

具体维护方法见官方题解http://codeforces.com/blog/entry/53567

AC code

#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define PI acos(-1) #define fi first #define se second #define INF 0x3f3f3f3f #define INF64 0x3f3f3f3f3f3f3f3f #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define ms(x,v) memset((x),(v),sizeof(x)) #define lc o<<1 #define rc o<<1|1 using namespace std; typedef long long LL; typedef long double DB; typedef pair<int,int> Pair; const double eps = 1e-8; const int maxn = 35000+10; int n,k; int dp[55][maxn]; //表示到第j个数分成了i段的最大价值 int tree[maxn<<2],lazy[maxn<<2]; int pre[maxn],pos[maxn]; inline void push_up(int o){ tree[o] = max(tree[lc],tree[rc]); } inline void push_down(int o){ if(lazy[o]){ tree[lc] += lazy[o]; tree[rc] += lazy[o]; lazy[rc] += lazy[o]; lazy[lc] += lazy[o]; lazy[o] = 0; } } void update(int ul,int ur,int L =1,int R = n,int o=1,int adv =1) { if(ul <= L && ur >= R){ tree[o] += adv; lazy[o] += adv; return; } push_down(o); int mid = (L+R) >>1; if(ul <= mid) update(ul,ur,L,mid,lc,adv); if(ur >mid)update(ul,ur,mid+1,R,rc,adv); push_up(o); } int query(int ql,int qr,int L =1,int R = n,int o =1){ if(ql<=L && qr >= R)return tree[o]; push_down(o); int mid = (L+R) >>1; int ans =0; if(ql <=mid) ans = max(ans,query(ql,qr,L,mid,lc)); if(qr >mid) ans = max(ans,query(ql,qr,mid+1,R,rc)); push_up(o); return ans; } void build(int *d,int L=1,int R=n,int o=1){ //以dp数组构建线段树 lazy[o] =0; if(L==R){ tree[o] = d[L-1];return; } int mid = (L+R)>>1; build(d,L,mid,lc); build(d,mid+1,R,rc); push_up(o); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; ms(pre,0); ms(pos,0); ms(dp,0); for(int i=1 ; i<=n ; ++i){ int x;cin>>x; pre[i] = pos[x] +1;//处理出i位置为ｘ的前一个ｘ的位置 pos[x] = i; } for(int i=1 ; i<=k ; ++i){ build(dp[i-1]); for(int j=1 ; j<=n ; ++j){ update(pre[j],j); dp[i][j] = query(1,j); } } std::cout << dp[k][n] << '\n'; return 0; }