「poj 2228」Naptime (环形DP)

poj 2228
题意:有一个环,选择一段长度为$n$进行计算。如果第i个时间点选择不睡觉那么就会增加$a_i$。你也可以选择睡觉,第一个时间点不算,睡觉时间至少为$m$。

先考虑线性做法,设$dp(i,j,0/1)$为前$i$个选了$j$个睡觉,$i$不选/选的最大值。
转移显然
$$
\begin{cases}
dp(i,j,0)=min(dp(i-1,j,0),dp(i-1,j,1)) \\
dp(i,j,1)=min(dp(i-1,j-1,0), dp(i-1,j-1,1)+a_i)
\end{cases}
$$
由于1位置一定不能对答案贡献,所以初值$dp(1, 0, 0)=dp(1, 1, 1)=0$,其他负无穷大
答案为$max(dp(n, b, 0), dp(n, b, 1))$
如果考虑环上做法,我们之前的做法相当于在$1$和$n$处断开了链,现在要将他强行接上去,我们可以这次强行选择$1,n$睡觉,然后再做一次DP,综合两者答案。
所以初值改为$dp(1, 0, 0)=0, dp(1, 1, 1)=a_i$,其他负无穷大
答案为$dp(n, b, 1)$
综合两者答案即可。注意要用滚动数组。

知识点:
1、环形不一定要复制两遍

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL INF = 4223372036854775808ll;
int n, b, a[3831];
LL dp[2][3831][2], ans;
void clean() {
ans = 0ll;
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= b; ++j) dp[i][j][0] = dp[i][j][1] = -INF;
}
int solve() {
scanf("%d%d", &n, &b);
clean();
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int cur = 1;
dp[1][0][0] = dp[1][1][1] = 0;
for (int i = 2; i <= n; ++i) {
cur ^= 1;
for (int j = 0; j <= min(i, b); ++j) {
dp[cur][j][0] = max(dp[cur ^ 1][j][0], dp[cur ^ 1][j][1]);
if (j - 1 >= 0) {
dp[cur][j][1] = max(dp[cur ^ 1][j - 1][0], dp[cur ^ 1][j - 1][1] + (LL)a[i]);
}
}
}
ans = max(dp[cur][b][0], dp[cur][b][1]);
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= b; ++j) dp[i][j][0] = dp[i][j][1] = -INF;
cur = 1;
dp[1][0][0] = 0, dp[1][1][1] = a[1];
for (int i = 2; i <= n; ++i) {
cur ^= 1;
for (int j = 0; j <= min(i, b); ++j) {
dp[cur][j][0] = max(dp[cur ^ 1][j][0], dp[cur ^ 1][j][1]);
if (j - 1 >= 0) {
dp[cur][j][1] = max(dp[cur ^ 1][j - 1][0], dp[cur ^ 1][j - 1][1] + (LL)a[i]);
}
}
}
ans = max(ans, dp[cur][b][1]);
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------