[Acwing] 4378. 选取数对 序列dp

前言

传送门 :

思路

状态表示
f [ i ] [ j ] : f[i][j] : f[i][j]: 前 i i i个点,并且选择了 k k k个区间的最大价值

状态计算 :

• 不选择当前 i i i端点为右端点
  f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]
• 选择当前的 i i i端点
  f [ i ] [ j ] = m a ( f [ i − 1 ] [ j ] , f [ i − m ] [ j − 1 ] + s u m [ i ] − s u m [ i − m ] ) f[i][j] = ma(f[i-1][j],f[i-m][j-1] +sum[i] - sum[i-m]) f[i][j]=ma(f[i−1][j],f[i−m][j−1]+sum[i]−sum[i−m])
  (从一个区间转移过来)

MyCode

int n,m,k;
cin>>n>>m>>k;

for(int i=1;i>a[i];
	sum[i] = sum[i-1] + a[i];
}




for(int i=1;i