学步园

/*
 * poj2228 AC
 * DP+滚动数组
 * 方程开始就想错了，看了题解才知道差了十万八千里。
 * 值得研究的一道题。
 *
 * f[i][j][0..1]表示前i段时间，休息j段时间，且第i段时间
 * 在不休息(0)或休息(1)时的最大值。
 *
 * f[i][j][0] = max(f[i-1][j][1],f[i-1][j][0]);
 * f[i][j][1] = max(f[i-1][j-1][1]+a[i],f[i-1][j-1][0]);
 *
 * 但以上方程中，时间段1始终不能取到，所以分两种情况：
 * 1) 时间段1不能取到，初始化f[0][0][0] = 0，其他为-INF。
 *  ans = max(f[n][b][1],f[n][b][1]);
 * 2) 时间段1能被取到，初始化f[0][1][1] = 0，其他为-INF。
 *  ans = max(f[n][b][0],f[n][b][1]+a[1]);
 * 
 * 下面这个解释更加清晰。
 * 转自：http://blog.csdn.net/xjwjava/article/details/6778549
 *
 * 接着考虑circle的问题：
 * 有两种方法：1、分情况讨论；2、在1～n后面接上多一段1～n。
 * 我是按照第一种方法做的，分三种情况讨论：
 * （1）第一段不睡，这样最后一段睡不睡都无所谓：
 * 边界为：f[1][0][0] = 0, f[1][1][1] = -INF
 * 结果为：max(f[n][b][0], f[n][b][1])
 * （2）第一段睡，最后一段也睡：
 * 边界为：f[1][1][1] = utility[1], f[1][0][0] = -INF
 * 结果为：f[n][b][1]
 * （3）第一段睡，最后一段不睡：
 * 边界为：f[1][1][1] = 0, f[1][0][0] = -INF
 * 结果为：f[n][b][0]
 *
 * 采用滚动数组节约空间开销。
 *
 * */
#include<cstdio>
#include<algorithm>
#define INF (1<<30)
using namespace std;

long f[2][3900][2],a[3900];

int main()
{
    int n,b,i,j,tmp;
    FILE* fin;
    fin = fopen("d.in","r");
//    scanf("%d%d",&n,&b);
    fscanf(fin,"%d%d",&n,&b);
    
    for(i=1;i<=n;i++)
//      scanf("%ld",&a[i]);
        fscanf(fin,"%ld",&a[i]);

    long ans = 0;
    for(j=0;j<=b;j++)
         f[0][j][1] = f[0][j][0] = -INF;
    f[0][0][0] = 0,tmp = 0;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=b;j++)
            f[1-tmp][j][1] = f[1-tmp][j][0] = -INF;
        for(j=0;j<=b;j++)
        {
            f[1-tmp][j][0] = max(f[tmp][j][0],f[tmp][j][1]);
            if(j>0)
                f[1-tmp][j][1] = max(f[tmp][j-1][0],f[tmp][j-1][1]+a[i]);
        }
        tmp = 1-tmp;
    }
    ans = max(f[tmp][b][1],f[tmp][b][0]);
    
    for(j=0;j<=b;j++)
         f[0][j][1] = f[0][j][0] = -INF;
    f[0][1][1] = 0,tmp = 0;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=b;j++)
            f[1-tmp][j][1] = f[1-tmp][j][0] = -INF;
        for(j=0;j<=b;j++)
        {
            f[1-tmp][j][0] = max(f[tmp][j][0],f[tmp][j][1]);
            if(j>0)
                f[1-tmp][j][1] = max(f[tmp][j-1][0],f[tmp][j-1][1]+a[i]);
        }
        tmp = 1-tmp;
    }
    ans = max(ans,max(f[tmp][b][0],f[tmp][b][1]+a[1]));
    
    printf("%ld\n",ans);
//    fclose(fin);
    return 0;                    
}