传送门
建议先做这道题,有一些套路是一模一样的。
考虑如何dp,dp[i][j]表示现在扫到第i个数,用了j段区间,最大的总价值,cnt(l,r)表示在区间[l,r]中不同的数的个数。
考虑在区间[1,p]分段,很容易列出dp方程:
dp[i][j]=max{dp[p][j−1]+cnt(p+1,i)}
其中$$1 \le p \le i-1$$
容易算出,枚举i复杂度为O(k),枚举p复杂度为O(n),计算cnt复杂度为O(n)
总复杂度为O(n2k),会TLE
考虑如何优化,发现复杂度瓶颈在寻找最大值和计算cnt,考虑线段树优化。
考虑计算数组lst[i],表示颜色a[i]上一次出现的地方,这个O(n) 在输入时预处理即可。
对于dp数组每一层,每次跑dp都重建一个线段树。
发现枚举到a[i],[lst[i],i−1]都要+1,因为只有对于区间[p,i](p∈[lst[i],i−1]),a[i]才算新出现的元素。
查询时,查询[0,j−1]dp数组最大值即可。
时间复杂度O(knlogn)
代码里面dp数组下标从0开始是为了更方便地计算[0,j−1]dp数组最大值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #include <bits/stdc++.h> #define MAXN 35005 #define MAXM 51 using namespace std; int dp[MAXM][MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r; int maxn,tag; }tree[MAXN<<2]; #define lc i<<1 #define rc i<<1|1 inline void pushup(int i){ tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn); } inline void pushdown(int i){ if (tree[i].tag){ tree[lc].tag+=tree[i].tag; tree[lc].maxn+=tree[i].tag; tree[rc].tag+=tree[i].tag; tree[rc].maxn+=tree[i].tag; tree[i].tag=0; } } void Build(int i,int lev,int l,int r){ tree[i].l=l,tree[i].r=r; tree[i].tag=0; if (l==r){ tree[i].maxn=dp[lev][l]; return ; } int mid=(l+r)>>1; Build(lc,lev,l,mid); Build(rc,lev,mid+1,r); pushup(i); } void Update(int i,int L,int R,int val){ if (L<=tree[i].l&&tree[i].r<=R){ tree[i].maxn+=val; tree[i].tag+=val; return ; } int mid=(tree[i].l+tree[i].r)>>1; pushdown(i); if (L<=mid) Update(lc,L,R,val); if (mid<R) Update(rc,L,R,val); pushup(i); } int Query(int i,int L,int R){ if (L<=tree[i].l&&tree[i].r<=R){ return tree[i].maxn; } int mid=(tree[i].l+tree[i].r)>>1,ans=0; pushdown(i); if (L<=mid) ans=max(ans,Query(lc,L,R)); if (mid<R) ans=max(ans,Query(rc,L,R)); return ans; } } using namespace SegmentTree; int lst[MAXN],lstcolor[MAXN]; int a[MAXN];
int main(){ int n=read(),k=read(); for (register int i=1;i<=n;++i){ a[i]=read(); lst[i]=lstcolor[a[i]]; lstcolor[a[i]]=i; } for (register int i=1;i<=k;++i){ Build(1,i-1,0,n); for (register int j=1;j<=n;++j){ Update(1,lst[j],j-1,1); dp[i][j]=Query(1,0,j-1); } } printf("%d\n",dp[k][n]); }
|