AcWing 4418. 选元素
原题链接
困难
作者:
浪里大白鲨
,
2022-05-09 23:32:12
,
所有人可见
,
阅读 207
O(n^3)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
/*
状态转移方程:f[i][j] = max(f[i - v][j - 1]); 0 <= v < i
i:从前i个元素中选择
j:选择元素个数
状态转移方程含义:每种状态来自,选择个数少1的最优选择
*/
const int N = 210;
int q[N];
long long f[N][N];
int n,m,k;
int main()
{
cin>>n>>k>>m;
memset(f,-0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++) cin>>q[i];
for(int i=1;i<=n;i++) //在前i个元素中选择,且已经选择第i个元素
for(int j=1;j<=m;j++) //选择个数为j
for(int v=max(i-k,0);v<i;v++) //每种状态的最优解
f[i][j]=max(f[i][j],f[v][j-1]+q[i]);
long long res=-1;
for(int i=0;i<k;i++) //没k个中必须选择一个,最后答案就在最后k个中
res=max(res,f[n-i][m]);
cout<<res<<endl;
return 0;
}