poj2228Naptime——环形DP

题目：http://poj.org/problem?id=2228

dp[i][j][0/1]表示前i小时中第j小时睡(1)或不睡(0)的最优值；

注意第一个小时，若睡则对最终取结果有要求，即第n个小时必须睡，所以据此DP两遍；

可以开滚动数组，否则容易MLE。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long ans,f[3][4000][2];
int n,u[4000],b;
int main()
{
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
        scanf("%d",&u[i]);
    memset(f,-2,sizeof f);
    f[1][0][0]=0;f[1][1][1]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(i,b);j++)
        {
            f[i%2][j][0]=max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
            if(j)f[i%2][j][1]=max(f[(i-1)%2][j-1][0],f[(i-1)%2][j-1][1]+u[i]);
        }
    for(int j=0;j<=b;j++)
        ans=max(ans,max(f[n%2][j][0],f[n%2][j][1]));
    memset(f,-2,sizeof f);
    f[1][1][1]=u[1];
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(i,b);j++)
        {
            f[i%2][j][0]=max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
            if(j)f[i%2][j][1]=max(f[(i-1)%2][j-1][0],f[(i-1)%2][j-1][1]+u[i]);
        }
    for(int j=0;j<=b;j++)
        ans=max(ans,f[n%2][j][1]);
    printf("%lld",ans);
    return 0;
}