Codeforces-834D The Bakery 线段树优化DP

给n个数，让你分成k个子段，让每个子段中不同数字个数的和最大

dp[i][j]：前i个元素分成j段的最大和

考虑第j段，他的开头为k，那么dp[i][j]=max{dp[k][j-1]+sum[k+1][i] | 0<=k<=i-1 }

节点i维护dp[k]+sum(k+1,i),0<=k<=i-1,k是上一段的结尾，即第j层外循环决定了第j个区间是[k+1,i]

#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
using namespace std;
#define ll long long
#define pb push_back
#define FOR(a) for(int i=1;i<=a;i++)
const int inf=0x3f3f3f3f;
const int maxn=3e5+9; 
const int mod=1e9+7;

int n,k;

int dp[maxn];

struct NODE{
	int maxx,lazy;
}ST[maxn<<2];

void pushup(int rt){ST[rt].maxx=max(ST[rt<<1].maxx,ST[rt<<1|1].maxx);}
void build(int l,int r,int rt){
	ST[rt].lazy=0;
	if(l==r){ST[rt].maxx=dp[l];return;}
	int m=l+r>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);
}
void pushdown(int rt){
	if(ST[rt].lazy){
		ST[rt<<1].lazy+=ST[rt].lazy;ST[rt<<1].maxx+=ST[rt].lazy;
		ST[rt<<1|1].lazy+=ST[rt].lazy;ST[rt<<1|1].maxx+=ST[rt].lazy;
		ST[rt].lazy=0;
	}
}
void update(int a,int b,int c,int l,int r,int rt){
	if(a<=l&&b>=r){ST[rt].maxx+=c;ST[rt].lazy+=c;return;}
	pushdown(rt);
	int m=l+r>>1;
	if(a<=m)update(a,b,c,l,m,rt<<1);
	if(b>m)update(a,b,c,m+1,r,rt<<1|1);pushup(rt);
}
int query(int a,int b,int l,int r,int rt){
	if(a<=l&&b>=r)return ST[rt].maxx;
	int m=l+r>>1,ans=0;
	if(a<=m)ans=query(a,b,l,m,rt<<1);
	if(b>m)ans=max(ans,query(a,b,m+1,r,rt<<1|1));
	return ans;
}

int arr[maxn],pre[maxn],lst[maxn];
int main(){
	scanf("%d%d",&n,&k);
	FOR(n){
		scanf("%d",&arr[i]);
		pre[i]=lst[arr[i]],lst[arr[i]]=i;
	}
	for(int j=1;j<=k;j++){	
		build(0,n,1);
		for(int i=1;i<=n;i++){	//枚举前i个元素
			update(pre[i],i-1,1,0,n,1);
			dp[i]=query(0,i-1,0,n,1);
		}
	}
	printf("%d
",dp[n]);
}

线段树DP。。之前多校也有一题，体感没这个难

仔细想想也是，DP的转移就是取max，因此用线段树维护DP值也没什么奇怪的

感觉果然好难，这就是目前自己的天花板了吧。。。。要加油啊!