BZOJ 1737 [Usaco2005 jan]Naptime 午睡时间

题目大意

一天是环形的，分为$X$段，每段都有一个价值，使用其中B段时间睡觉，每一个睡觉时间区间的第一段时间将不会计算价值，因为是环形所以从晚上睡到早上也是一段，求最大价值。

自己想出来的哈哈哈

考虑$F_{i,j}$表示到$i$段睡了$j$段本时段不睡的最大价值，$G_{i,j}$表示到$i$段睡了$j$段本时段睡的最大价值，所以有状态转移方程

$F_{i,j} = \min(F_{i-1,j},G_{i-1,j})$

$G_{i,j} = \min(F_{i-1,j-1},G_{i-1,j-1}+Val_i)$

之后考虑第一时间和最后一个时间都睡的情况。直接钦定最后时间和第一时间都睡所以第二次DP就是让第一天睡觉也获得价值，最后就取$N$段本段睡的价值，取个min就可以了。

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