算法1
(暴力枚举) $O(n^2)$
由于f[n,m,2]元三维表示会MLE 注意到 状态转移方程 i与i+1只有线性的关系,因此可以优化掉第一维,变成f[m][2]
然后根据蓝书推导的递推方程即可
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 3850;
const int INF = 0x3f3f3f3f;
int f[N][2];
int n,m;
int w[N];
signed main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++) cin >> w[i];
memset(f,-0x3f,sizeof f);
f[0][0] = 0;// f[1][1] = 0;
for(int i = 1;i<=n;i++)
for(int j = min(i,m);j>=1;j--){
f[j][0] = max(f[j][0] , f[j][1]);
f[j][1] = max(f[j-1][0] , f[j-1][1] + w[i]);
}
int ans1 = max(f[m][0],f[m][1]);
// cout << ans1 << endl;
memset(f,-0x3f,sizeof f);
f[1][1] = w[1];
// f[0][0] = 0;
for(int i = 2;i<=n;i++) //第一天已选 不考决策第一天选与不选的情况
for(int j = min(i,m);j>=1;j--){
f[j][0] = max(f[j][0] , f[j][1]);
f[j][1] = max(f[j-1][0] , f[j-1][1] + w[i]);
}
int ans2 = f[m][1];
cout << max(ans1,ans2) << endl;
return 0;
}