HDU 5208 Where is Bob
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5208
题目翻译
两个区间，(\left [ l1,r1 \right ]) 与 (\left [ l2,r2 \right ])，Alice在第一个区间里选择一个数字(x)，之后JSL在第二个区间里选择一个数字(y)。最终结果(z=x XOR y)，Alice期望数字尽量小，JSL期望数字尽量大。求(z)的值。
题解
类似数位DP，我们按照每一个二进制位来处理，对于Alice的每一个的选择，JSL一定会尽可能地让自己这一位和Alice相同，从而使这一位消掉。
所以，我们数位DP，Alice的选择，贪心处理JSL的选择。
DP[pos][upAlice][downAlice][upJSL][downJSL]表示当前pos位的时候，两个人这一位的上下界情况如上的最大值。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int dp[35][5][5][5][5]; int l1,r1,l2,r2; int DP(int pos,int up1,int down1,int up2,int down2){ if (pos<0) return 0; if (dp[pos][up1][down1][up2][down2]!=-1) return dp[pos][up1][down1][up2][down2]; int leftUp=up1?((r1>>pos)&1):1; int leftDown=down1?((l1>>pos)&1):0; int rightUp=up2?((r2>>pos)&1):1; int rightDown=down2?((l2>>pos)&1):0; int ret=0; for (int now=leftDown;now<=leftUp;now++){ if (rightDown<=now && now<=rightUp){ ret=max(ret,DP(pos-1,up1&&now==leftUp,down1&&now==leftDown,up2&&now==rightUp,down2&&now==rightDown)); }else{ ret=max(ret,(1<<pos)+DP(pos-1,up1&&now==leftUp,down1&&now==leftDown,up2&&(now^1)==rightUp,down2&&(now^1)==rightDown)); } } return dp[pos][up1][down1][up2][down2]=ret; } inline void solve(int T){ scanf("%d%d%d%d",&l1,&r1,&l2,&r2); memset(dp,-1,sizeof(dp)); printf("Case #%d: %d\n",T,DP(30,1,1,1,1)); } int main(){ int T=0; while(scanf("%d",&T)!=EOF){ for (int i=1;i<=T;i++){ solve(i); } } return 0; } |
原文链接：HDU 5208 Where is Bob
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!