Submit: 859 Solved: 356
[Submit][Status][Discuss]
Description
一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。
l A的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。
l B的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。
和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。你的任务是判断谁会赢，需要多少回合。
比如n=2，白棋子在(1,1)，黑棋子在(2,2)，那么虽然A有两种走法，第二个回合B总能取胜。
Input
输入仅一行，包含五个整数n, r1, c1, r2, c2，即棋盘大小和棋子位置。白色棋子在(r1,c1)，黑色棋子在(r2,c2)（1<=r1,c1,r2,c2<=n）。黑白棋子的位置保证不相同。
Output
输出仅一行，即游戏结果。如果A获胜，输出WHITE x；如果B获胜，输出BLACK x；如果二者都没有必胜策略，输出DRAW。
Sample Input
2 1 1 2 2
Sample Output
BLACK 2
HINT
n<=20
题解：暴力DP即可；
f[i][j][k][l][m][n]:表示：第I位，第一，二，三个数用了i,j,k个，n表示是否有进位；
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define clr(a,b) memset(a,b,sizeof(a)) 4 typedef long long ll; 5 const ll inf=0x3f3f3f3f3f3f3f3fll; 6 ll a,b,c; 7 ll la,lb,lc,len; 8 ll dp[62][40][40][40][2]; 9 void getlen(){len=max(log2(a)+1,max(log2(b)+1,log2(c)+1));} 10 ll getnum(ll x) 11 { 12 ll sum=0; 13 for(int i=0;i<62;++i) {if( x & (1ll<<i) ) sum++; } 14 return sum; 15 } 16 void work() 17 { 18 dp[0][0][0][0][0]=0; 19 for(ll i=0;i<len;++i) 20 { 21 for(ll j=0;j<=la;++j) 22 { 23 for(ll k=0;k<=lb;++k) 24 { 25 for(ll l=0;l<=lc;++l) 26 { 27 long long tmp=dp[i][j][k][l][0];//枚举最后一位不进位的情况 28 dp[i+1][j+1][k+1][l+1][1]=min(dp[i+1][j+1][k+1][l+1][1],tmp+(1<<i+1)); 29 dp[i+1][j+1][k][l+1][0]=min(dp[i+1][j+1][k][l+1][0],tmp+(1<<i)); 30 dp[i+1][j][k+1][l+1][0]=min(dp[i+1][j][k+1][l+1][0],tmp+(1<<i)); 31 dp[i+1][j][k][l][0]=min(dp[i+1][j][k][l][0],tmp); 32 tmp=dp[i][j][k][l][1];//枚举最后一位进位的情况 33 dp[i+1][j+1][k+1][l+1][1]=min(dp[i+1][j+1][k+1][l+1][1],tmp+(1<<i+1)); 34 dp[i+1][j][k+1][l][1]=min(dp[i+1][j][k+1][l][1],tmp+(1<<i)); 35 dp[i+1][j+1][k][l][1]=min(dp[i+1][j+1][k][l][1],tmp+(1<<i)); 36 dp[i+1][j][k][l][0]=min(dp[i+1][j][k][l][0],tmp); 37 } 38 } 39 } 40 } 41 //cout<<len<<" "<<la<<" "<<lb<<" "<<lc<<endl; 42 if(dp[len][la][lb][lc][0]>=inf) printf("-1 "); 43 else printf("%d ",dp[len][la][lb][lc][0]); 44 } 45 46 int main() 47 { 48 scanf("%lld%lld%lld",&a,&b,&c); 49 getlen(); memset(dp,inf,sizeof dp); 50 la=getnum(a);lb=getnum(b);lc=getnum(c); 51 work(); 52 return 0; 53 }