AcWing 288. 休息时间
原题链接
中等
作者:
总有刁民想害朕
,
2020-04-14 10:46:19
,
所有人可见
,
阅读 844
思路分析
环形问题的一种解决策略:两次dp法,第一次dp在任意位置断开成链,按照线性问题求解,第二次dp把断开的位置是环的时候第一次dp忽略的情况补充上,一般就是初值不同
本题思路:我们第一次dp从1处断开,变成从1-N的线性序列,再从中选b小时,按照线性问题求解,1处属于第一个小时,一定不会获得价值,我们再考虑忽略的情况,那就是环的情况下,1处可能会有价值,我们需要把这种情况补上,补上的表现就是dp的初值不同
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 4000, INF = 0x3f3f3f3f;
int w[N];
int dp[2][N][2];//表示前i个小时中休息了j个小时,并且第i个小时为0 和 1 的状态,(0):没有休息,(1):休息
int n, m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n;++i) cin >> w[i];
//在1处破环成链
memset(dp, -0x3f, sizeof dp);
dp[1][0][0] = 0;dp[1][1][1] = 0;
for(int i = 2;i <= n;++i)
for(int j = 0;j <= m;++j){
dp[i%2][j][0] = max(dp[(i-1)%2][j][0], dp[(i-1)%2][j][1]);
if(j)
dp[i%2][j][1] = max(dp[(i-1)%2][j-1][0], dp[(i-1)%2][j-1][1] + w[i]);
}
int ans = max(dp[n%2][m][0], dp[n%2][m][1]);
//补充剩下的情况,1处是环的情况
memset(dp, -0x3f, sizeof dp);
dp[1][1][1] = w[1];
for(int i = 2;i <= n;++i)
for(int j = 0;j <= m;++j){
dp[i%2][j][0] = max(dp[(i-1)%2][j][0], dp[(i-1)%2][j][1]);
if(j)
dp[i%2][j][1] = max(dp[(i-1)%2][j-1][0], dp[(i-1)%2][j-1][1] + w[i]);
}
ans = max(ans, dp[n%2][m][1]);
cout << ans << endl;
}