题目链接 给一个序列，要求把序列划分成k段,每一段里的权值是这一段里不同数字的个数。求如何划分使得k个区间的权值和最大。 我们容易想到dp[i][j]代表前j个分为i段时的最大值
dp[i][j] = dp[i-1][k] + size(k+1 , j) ( 0<=k<j ) //size(a,b)表示a到b这个区间里有多少个不同数字但是这显然是个二维的方程，比赛时怎么都想不到，赛后看题解看到了很巧妙的解决方法。 当枚举到num[j]的时候，把num[j]这个数字最近一次出现的位置记录一下p，然后把dp[i-1][p]到dp[i-1][j-1]加上1，然后dp[i][j] = max(dp[i-1][k]) ( i-1<=k < j) 其实这里的dp[i][k]存的是当前枚举到j时从k+1开始开始重启一段能够获得的价值。[ 这个地方可以算是求不同颜色的一种方法(get到新知识) ],于是我们在查询和加1的操作都可以通过线段树来维护.
#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, m , 1 int dp[55][40000] ; int N , K ; int pos[40000] ; int num[40000] ; int tree[35000 * 4 + 2000] ; int lazy[35000*4 +2000] ; void Push_up(int rt) { tree[rt] = max (tree[rt<<1] , tree[rt<<1|1]) ; } void Build(int l ,int r ,int rt , int x) { lazy[rt] = 0 ; if(l == r) { tree[rt] = dp[x][l] ; return ; } int mid = (l + r) /2 ; Build(l , mid , rt<<1 , x) ; Build(mid + 1, r , rt<<1|1 , x) ; Push_up(rt) ; } void Push_down( int rt) { if(lazy[rt]) { tree[rt<<1] += lazy[rt] ; tree[rt<<1|1] += lazy[rt] ; lazy[rt<<1] += lazy[rt] ; lazy[rt<<1|1] += lazy[rt] ; lazy[rt ] = 0 ; } } void Update(int L, int R , int l ,int r , int rt ) { if(L <= l && r <= R) { tree[rt] ++ ; lazy[rt] ++ ; return ; } int mid = (l +r) / 2; Push_down(rt) ; if(L <= mid ) Update( L ,R , l ,mid ,rt<<1 ) ; if( R > mid ) Update(L ,R , mid + 1, r , rt<<1|1 ) ; Push_up(rt ) ; } int Que(int L ,int R , int l ,int r ,int rt) { if(L <= l &&r <= R) { return tree[rt] ; } int mid = ( l + r) / 2; int res =0 ; Push_down(rt) ; if(L <= mid) res = max(res , Que(L , R , l , mid , rt << 1) ) ; if(R > mid ) res = max(res , Que(L , R , mid + 1 , r , rt <<1|1 ) ) ; return res ; } int main() { cin>> N >> K ; clr0(pos) ; clr0(dp) ; // num[1] = 0; for(int i = 1; i<= N ; ++ i) scanf("%d",&num[i]) ; // cout<<"FSDFGFD"; for(int j = 1; j<= N ; ++j) if(!pos[num[j]]) dp[1][j] =dp[1][j-1]+1 , pos[num[j]] = j ; else dp[1][j] = dp[1][j-1] ; for(int i = 2 ; i<= K ; ++ i) { clr0(pos ) ; Build(1,N,1,i-1) ; for(int j = i ; j<= N ; ++ j) { int t = pos[num[j]] ; if(!t) t = 1; Update(t , j-1 , 1, N ,1) ; int res = 0 ; res = Que(i-1 ,j-1 , 1 , N ,1); dp[i][j] = res ; pos[num[j]] = j ; } } cout<<dp[K][N]<<endl; }