CodeForces 833B The Bakery ——dp+线段树

CodeForces 833B The Bakery ——dp+线段树

​

#include #include #include #include #include using namespace std;const int maxn = 5e4 + 10;int a[maxn], pos[maxn], pre[maxn], dp[100][maxn];struct Seg_Tree{ int value[maxn<<2],lazy[maxn<<2]; void clear(){ memset(value,0,sizeof(value)); memset(lazy,0,sizeof(lazy)); } void Down(int x){ int lc = x<<1,rc = x<<1|1; value[lc]+=lazy[x]; value[rc]+=lazy[x]; lazy[lc]+=lazy[x]; lazy[rc]+=lazy[x]; lazy[x]= 0; } void Up(int x){ value[x]=max(value[x<<1],value[x<<1|1]); } void Update(int x,int l,int r,int L,int R,int delta){ if (l>R||r>1; Update(x<<1,l,Mid,L,R,delta); Update(x<<1|1,Mid+1,r,L,R,delta); Up(x); } void Update1(int x,int l,int r,int index,int delta){ if (l==r){ value[x]+=delta; return; } if (lazy[x]){ Down(x); } int Mid = (l+r)>>1; if (index<=Mid){ Update1(x<<1,l,Mid,index,delta); }else{ Update1(x<<1|1,Mid+1,r,index,delta); } Up(x); } int getMax(){ return value[1]; }}tree;int main() { int n, m; scanf("%d%d", &n, &m); int cnt = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (!pos[a[i]]) cnt++; pre[i] = pos[a[i]]; pos[a[i]] = i; } for (int i = 1; i <= m; i++) { tree.clear(); for (int j = 1; j <= n; j++) { tree.Update(1, 0, n, pre[j], j-1, 1); tree.Update1(1, 0, n, j-1, dp[i-1][j-1]); dp[i][j] = tree.getMax(); } } printf("%d\n", dp[m][n]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。