Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 1707 | Accepted: 657 |
Description
The first player will choose from the pool a number x1 lying in [a, b] (0 < a < b), which means a <= x1 <= b. Next the second player should choose a number y1 such that y1 - x1 lies in [a, b] (Attention! This implies y1 > x1 since a > 0). Then the first player
should choose a number x2 such that x2 - y1 lies in [a, b]... The game ends when one of them cannot make a choice. Note that a player MUST NOT skip his turn.
A player's score is determined by the numbers he has chose, by the way:
player1score = x1 + x2 + ...
player2score = y1 + y2 + ...
If you are player1, what is the maximum score difference (player1score - player2score) you can get? It is assumed that player2 plays perfectly.
Input
contains n integers, the numbers in the pool, any of which lies in [-9999, 9999].
Output
Sample Input
3 6 1 2 1 3 -2 5 -3 6 2 1 2 -2 -1 2 1 2 1 0
Sample Output
-3 0 1
Source
题意:2个人轮流拿数组里面的一个数,且要比另外一个人上一次拿的数大【a,b】,第一次拿要拿【a,b】范围的数
题解:听说这是一道博弈dp什么,由于第一次听,就拿了这题理解了一下,我的理解如下
对于每一个人其实的状态都是要取自己的值减去别人的值尽量大,那么设dp【i】为本轮取了i后获得的最大值
由于下一轮是要使他的值最大,就是会使本轮的值最小,那么一定会选一个可以调转的使对方值最小的状态,所以
dp【i】=min(dp【i】,c【j】-dp【j】),其中a《=c【j】-c【i】《=b,并且j是别人挑选的,所以会使本轮的dp值最小
#include<stdio.h> #include<string.h> #include<algorithm> #define inf 100000008 using namespace std; int c[10008],dp[10008]; int main() { int t,n,a,b,i,j; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&a,&b); for(i=0;i<n;i++) { scanf("%d",c+i); dp[i]=inf; } sort(c,c+n); dp[n-1]=c[n-1]; for(i=n-2;i>=0&&c[i]>=a;i--) { for(j=i+1;j<n&&c[j]-c[i]<=b;j++) { if(c[j]-c[i]>=a) dp[i]=min(dp[i],c[i]-dp[j]); } if(dp[i]==inf) dp[i]=c[i]; } int res=-inf; for(i=0;i<n&&c[i]<=b;i++) { if(c[i]<a) continue; if(dp[i]>res) res=dp[i]; } if(res==-inf) printf("0\n"); else printf("%d\n",res); } return 0; }