状态转移
设f[i][j][0/1]
表示在第i个小时睡或不睡,睡j个小时的恢复的最大体力值
不难得出
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0])
f[i][j][1] = max(f[i-1][j-1][1] + w[i], f[i-1][j-1][0])
关于状态初始化的时候分类讨论下当天最后一小时睡与不睡,即:
第n小时不睡觉
memset(f, -0x3f, sizeof f);
f[1][0][0] = f[1][1][1] = 0;
第n小时睡觉
memset(f, -0x3f, sizeof f);
f[1][0][0] = 0; f[1][1][1] = w[1];
但是经过计算,该数组内存会超限
64mb = 1.6 * 10 ^ 7
数组占用内存 3.2 * 10 ^ 7
不难发现,当前状态与最近两层有关系,所以再用滚动数组优化
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3850;
int f[2][N][2], w[N];
int n, m;
inline void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
memset(f, -0x3f, sizeof f);
f[1][1][1] = f[1][0][0] = 0;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
if (j >= 1)
f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
}
int res = f[n & 1][m][0];
memset(f, -0x3f, sizeof f);
f[1][0][0] = 0; f[1][1][1] = w[1];
for (int i = 2; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i & 1][j][0] = max(f[i - 1 & 1][j][1], f[i - 1 & 1][j][0]);
if (j >= 1)
f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][1] + w[i], f[i - 1 & 1][j - 1][0]);
}
if (res < f[n & 1][m][1]) cout << f[n & 1][m][1] << endl;
else cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}