Lflame

【2016/3/8 考题】 War DP神题Orzzz

    题意 : A 和 B 要吃糖果 , 糖果放在一个栈中,从栈顶到栈底依次编号为 1 - N,每个糖果有两个属性 ri、si,分别表示这个糖果的营养值和美味值。A 和 B 轮流做操作,操作有以下两个 :

        Pass : 消耗一点能量,直接轮到对方。

        Eat : 吃掉栈顶的糖果,能量增加这个糖果的营养值,并且获得这个糖果的美味值。 (注意这个操作不会消耗一点能量)。

     A 先手,问 A 能够获得的最大美味值是多少。

    (N <= 150 , sigma{si} <= 150 , ri<=10^9)


    首先,很显然的,若一个人的能量小于另一个人,那么这个人就没有跳过这个糖果的权限,因为Pass过后,对方也可以Pass一遍。于是我们只关心能量的差值。

    于是暴力做法 : f[i][j] 表示还剩 i 个糖果,先手与后手能量值的差值为 j 时,先手能够获得的最大美味值。

    但是, ri <= 10^9 , 甚至连状态都存不下。


    不过在数据范围中,sigma{si}<=150,这是在提醒我们要将美味值放入状态,但是怎么放呢 ?

    dp[i][j] 表示只考虑第 i 个糖果到第 n 个糖果,先手想要获得至少 j 的美味值,最少需要先手与后手能量差值为多少。

    令 sum 表示第 i 个糖果到第 n 个糖果美味值的总和。

    (1)若先手选择 Eat ,那么就不能让后手获得超过 sum-j 的美味值,也就是说,要让 dp[i+1][sum-j+1] 不能达成,这意味着使得轮到后手时,后手与先手的差值小于 dp[i+1][sum-j+1] 。 

    写成式子即 : -(dp[i][j]+r[i])<dp[i+1][sum-j+1] 

    变形得到 : dp[i][j] >= -dp[i+1][sum-j+1]-r[i]+1。 这个式子代表着,要使得先手选择 Eat 后,能获得不少于 j 的美味值,先手与后手能量值的差值至少为 -dp[i+1][sum-j+1]-r[i]+1。

    (2)若先手选择 Pass,首先这需要先手有选择 Pass 的权限,并且,此时相当于将第 i 个糖果给后手吃(因为这时后手没有Pass权限),然后又轮到先手在 i+1 处做操作。要使得先手获得至少 j 的美味值,这代表着Pass后,先手能获得至少 j 的美味值,即使得 dp[i+1][j] 能够达成。

    写成式子即 : dp[i][j]-1-r[i] >= dp[i+1][j]

    变形得 : dp[i][j] >= dp[i+1][j]+r[i]+1 。

    但是注意,由于先手有权限选择Pass,也就是说,要满足dp[i][j]>=1。于是最后的式子 : dp[i][j] >= max(dp[i+1][j]+r[i]+1 , 1) 


    由于Eat 和 Pass 是由先手决定,于是最后转移即为 :

   dp[i][j]=min(-dp[i+1][sum-j+1]-r[i]+1 , max(dp[i+1][j]+r[i]+1 , 1) )

    答案即为满足 dp[1][j] <= A-B 的最大的 j 。


    代码 :

    

#include<iostream>

#include<ctime>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;


int n ;

int R[160] , S[160] ;

int A,B;

int sum[160] ;

int r[160] , s[160] ;

long long dp[160][160] ;


int main()

{

scanf("%d%d%d",&n,&A,&B) ;

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

scanf("%d%d",&r[i],&s[i]) ;

}

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

sum[i]=s[i]+(i==n?0:sum[i+1]) ;

}

memset(dp,0x3f,sizeof(dp)) ;

long long INF=dp[0][0] ;

for(int j=0;j<=s[n];++j)dp[n][j]=-INF ;

for(int i=n-1;i>=1;--i){

for(int j=0;j<=sum[1];++j){

long long eat=INF , pass=INF ;

if(sum[i]-j+1>=0)eat=-dp[i+1][sum[i]-j+1]-r[i]+1 ;

pass=max(dp[i+1][j]+r[i]+1,1ll) ;

dp[i][j]=min(eat,pass) ;

}

}

for(int j=sum[1];j>=0;--j){

if(dp[1][j]<=A-B){

printf("%d %d\n",j,sum[1]-j) ;

return 0 ;

}

}

return 0 ;

}


评论

热度(2)