[BZOJ5046]分糖果游戏

题目大意：
　　有a,b两个人分糖，每个人都有一个能量值。
　　每个人每一轮可以选择进行两种操作：
　　　　1.取走最左边的糖果，补充相应的能量值并获取相应的美味度。
　　　　2.跳过这一轮，能量值-1.
　　问在每个人都采取最优决策的情况下，每个人能获得最多的美味度是多少？

思路：
　　动态规划。
　　f[i][j]表示吃第i~n的糖，并获得j的美味度，两人能量值之差最小是多少。
　　如果轮到的人选择吃，那么f[i][j]=-f[i+1][suf[i]-j+1]-r[i]+1；
　　如果不吃，那么f[i][j]=max(f[i+1][j]+r[i]+1,1)。
　　不吃的时候要满足能量值之差>=1，因为对方同样可以通过不吃补回来。
　　最后的答案k为满足f[0][k]<=a-b的最大值，糖果最后一定能吃完，所以只要减一下就得到了两个答案。

#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long int64;
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int64 inf=0x4000000000000000ll;
const int N=151;
int r[N],s[N],suf[N];
int64 f[2][N];
int main() {
    const int n=getint(),a=getint(),b=getint();
    for(register int i=0;i<n;i++) {
        r[i]=getint(),s[i]=getint();
    }
    for(register int i=n-1;~i;i--) {
        suf[i]=suf[i+1]+s[i];
    }
    for(register int i=0;i<=s[n-1];i++) {
        f[!(n&1)][i]=-inf;
    }
    for(register int i=s[n-1]+1;i<=suf[0];i++) {
        f[!(n&1)][i]=inf;
    }
    for(register int i=n-2;~i;i--) {
        for(register int j=suf[i];~j;j--) {
            if(s[i]>=j) {
                f[i&1][j]=-inf;
                while(j--) f[i&1][j]=-inf;
                break;
            }
            f[i&1][j]=-f[!(i&1)][suf[i]-j+1]-r[i]+1;
            if(j<=suf[i+1]) {
                f[i&1][j]=std::min(f[i&1][j],std::max(1ll,f[!(i&1)][j]+r[i]+1));
            }
        }
    }
    for(register int i=suf[0];~i;i--) {
        if(f[0][i]<=a-b) {
            printf("%d %d
",i,suf[0]-i);
            return 0;
        }
    }
}