[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^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int64 inf=0x4000000000000000ll;

 const int N=;

 int r[N],s[N],suf[N];

 int64 f[][N];

 int main() {

     const int n=getint(),a=getint(),b=getint();

     for(register int i=;i<n;i++) {

         r[i]=getint(),s[i]=getint();

     }

     for(register int i=n-;~i;i--) {

         suf[i]=suf[i+]+s[i];

     }

     for(register int i=;i<=s[n-];i++) {

         f[!(n&)][i]=-inf;

     }

     for(register int i=s[n-]+;i<=suf[];i++) {

         f[!(n&)][i]=inf;

     }

     for(register int i=n-;~i;i--) {

         for(register int j=suf[i];~j;j--) {

             if(s[i]>=j) {

                 f[i&][j]=-inf;

                 while(j--) f[i&][j]=-inf;

                 break;

             }

             f[i&][j]=-f[!(i&)][suf[i]-j+]-r[i]+;

             if(j<=suf[i+]) {

                 f[i&][j]=std::min(f[i&][j],std::max(1ll,f[!(i&)][j]+r[i]+));

             }

         }

     }

     for(register int i=suf[];~i;i--) {

         if(f[][i]<=a-b) {

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

             return ;

         }

     }

 }

巴特西

[BZOJ5046]分糖果游戏

最新文章

热门文章