POJ 2228 Naptime 环形DP

先不考虑环的情况
dp[i][j][0]:前i个时间间隔中，已经花费了j个间隔，取得的最大值，并且第i个间隔在休息
dp[i][j][1]:前i个时间间隔中，已经花费了j个间隔，取得的最大值，并且第i个间隔不休息

转态转移

dp[i&1][j][1] = max(dp[(i+1)&1][j][0],dp[(i+1)&1][j][1]);
dp[i&1][j][0] = max(dp[(i+1)&1][j-1][0] + a[i],dp[(i+1)&1][j-1][1]);

最后的结果 ans = max(dp[N][B][0],dp[N][B][1])

考虑成环
由于N值过大，将输入变成两倍接到后面的做法不可取，tle

我们先令dp[1][1][0] = a[1],即在上一天最后一个时间段一定在sleep
然后重新运行DP，这样除了最后一段时间和第一段时间，其他的时间段都是成环之后的正确值。
我们再来看第一段和最后一段
在最后一段sleep的情况下，第一段显然是正确的
这是我们取 ans = max(ans,dp[N][B][0]),即最后一段时间一定在睡觉即可。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <limits.h>

using namespace std;

#define debug(x) cout<<#x<<": "<<x<<endl;

int N,B;
int a[3831];
int dp[2][3031][2];

void disp(){
    for(int i=0;i<=N;i++){
        for(int j=0;j<=B;j++){
            cout<<dp[i][j][0]<<" ";
            cout<<dp[i][j][1]<<" ";
            cout<<" ";
        }
        cout<<endl;
    }

}
int main()
{

    while( scanf("%d%d",&N,&B)!=EOF ){
        memset(dp,0x80,sizeof(dp));
        int ret = -1;
        for(int i=1;i <= N;i++){
            scanf("%d",&a[i]);
        }
        dp[1][0][1] = 0;
        dp[1][1][0] = 0;

        for( int i = 2;i <= N;i ++ ){
            for(int j = 0;j <= B;j ++){
                dp[i&1][j][1] = max(dp[(i+1)&1][j][0],dp[(i+1)&1][j][1]);
                if(j){
                    dp[i&1][j][0] = max(dp[(i+1)&1][j-1][0] + a[i],dp[(i+1)&1][j-1][1]);
                }
            }
        }

        //debug(111)
        ret = max(dp[N&1][B][0],dp[N&1][B][1]);


        memset(dp,0x80,sizeof(dp));
        dp[1][1][0] = a[1];
        for(int i=2;i<=N;i++){
            for(int j=0;j<=B;j++){
                dp[i&1][j][1] = max(dp[(i+1)&1][j][0],dp[(i+1)&1][j][1]);
                if(j){
                    dp[i&1][j][0] = max(dp[(i+1)&1][j-1][0]+a[i],dp[(i+1)&1][j-1][1]);
                }
            }
        }
        //disp();
        //ret = max(ret,dp[N&1][B][1]);
        ret = max(ret,dp[N&1][B][0]);

        cout<<ret<<endl;
    }
    return 0;
}