BZOJ 5046 分糖果游戏

网页崩溃了 心态也崩溃了 MD劳资写了那么多

题意：

类似于两个人博弈的问题 第一步想到的应该是f[i]=min(max(x)) 大概长这样的方程 但是我们发现做不下去

于是我们发现这个题非常神仙 令$f[i][j]$表示取完i~n的所有糖果先手拿到美味度至少为j的先后手能量值之差最小是多少

由于让来让去显然只看能量差的正负 那么我们可以通过维护这个玩意达到目的

显然这个玩意是非严格单调增的

接下来我们考虑两种操作

1.取走糖果 也就是先手达到了j+v[i]的美味度 所以后手达到的美味度一定不能达到suf[i]-j+1 并且他也不能达到这么大的能量差

显然我们可以得到状态转移方程 $f[i][j]=-(f[i+1][suf[i]-j+1]-1)+r[i]$

2.让 也就是说后手一定取走了这颗糖果 于是先后手顺序其实是没有变化的 这时候我们要先保证能量差>=1才能让出去

也就是(A-1-(B+r[i]))（A是先手 B是后手）要取得j的美味度于是得到转移$f[i][j]=max(1,f[i+1][j]+r[i]+1)$

（是不是感觉第二种转移挺反人类的 我也这么觉得）

于是这道题愉快的做完了 这个思路还是可以借鉴一下 但是真的好神仙啊qaq

//Love and Freedom.

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#define ll long long

#define inf 2002122520021225ll

#define N 151

#define M 22501

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch<'' || ch>'')    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')    s=s*+ch-'',ch=getchar();

    return f*s;

}

ll f[N][N]; int suf[N],n,A,B,r[N],v[N];

int main()

{

    n=read(),A=read(),B=read();

    for(int i=;i<=n;i++)    r[i]=read(),suf[i]=v[i]=read();

    for(int i=n-;i;i--)    suf[i]+=suf[i+];

    for(int i=;i<=v[n];i++)    f[n][i]=-inf;

    for(int i=v[n]+;i<=suf[];i++)    f[n][i]=inf;

    for(int i=n-;i;i--)    for(int j=;j<=suf[i];j++)

    {

        if(v[i]>=j)    f[i][j]=-inf;

        else    f[i][j]=-f[i+][suf[i]-j+]+-r[i];

        ll tmp=max(1ll,f[i+][j]+r[i]+);

        if(j<=suf[i+])    f[i][j]=min(f[i][j],tmp);

    }

    int fin=;

    for(int i=;i<=suf[] &&(ll)A-B>=f[][i];i++)    fin=i;

    printf("%d %d\n",fin,suf[]-fin);

    return ;

}