本文主要是介绍hdu5208 Where is Bob 数位dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
维护四个数的上下边界条件，转移使最小值最大即可。
数位dp有时只对dp赋一次-1，这时边界条件满足一定条件与后面的数是什么无关，可以直接返回，在此题中条件太苛刻，用处不大，会tle。
也可以每次都赋一次-1，这时算出一个状态的值就能赋给dp，再次用到时直接返回。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#define fi first
#define se second
#define debug puts("=======")
#define pii pair<int,int>
#define ll long long
#define inf ((ll)1<<60)
#define eps 1e-8
using namespace std;
const int maxn=100005;
int l1,r1,l2,r2;
int d1[35],d2[35];
int p1[35],p2[35];
ll dp[35][2][2][2][2];
ll tot[35];
ll dfs(int id,int f1,int f2,int f3,int f4)
{if(id==-1) return 0;if(dp[id][f1][f2][f3][f4]!=-1)return dp[id][f1][f2][f3][f4];int mi,mx;if(f2)mx=d2[id];elsemx=1;if(f1)mi=d1[id];elsemi=0;int Mi,Mx;if(f4)Mx=p2[id];elseMx=1;if(f3)Mi=p1[id];elseMi=0;ll ans=0;for(int i=mi;i<=mx;i++) {ll u=inf;for(int j=Mi;j<=Mx;j++) {ll v=dfs(id-1,f1&&i==mi,f2&&i==mx,f3&&j==Mi,f4&&j==Mx);if((i^j))v+=tot[id];u=min(u,v);}ans=max(ans,u);}dp[id][f1][f2][f3][f4]=ans;return ans;
}
ll solve()
{int p;for(int i=0;i<=30;i++) {d1[i]=d2[i]=p1[i]=p2[i]=0;}int cnt=0;while(l1) {d1[cnt++]=l1%2;l1/=2;}p=cnt;cnt=0;while(r1) {d2[cnt++]=r1%2;r1/=2;}p=max(p,cnt);cnt=0;while(l2) {p1[cnt++]=l2%2;l2/=2;}p=max(p,cnt);cnt=0;while(r2) {p2[cnt++]=r2%2;r2/=2;}p=max(p,cnt);memset(dp,-1,sizeof(dp));return dfs(p,1,1,1,1);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("wa.txt","w",stdout);tot[0]=1;for(int i=1;i<35;i++)tot[i]=tot[i-1]*2;int t;int cas=1;scanf("%d",&t);memset(dp,-1,sizeof(dp));while(t--) {scanf("%d%d%d%d",&l1,&r1,&l2,&r2);printf("Case #%d: %I64d\n",cas++,solve());}return 0;
}这篇关于hdu5208 Where is Bob 数位dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
