HDU 5803（2016多校第6场） 数位dp
zjhl2
posted @ 2016年8月05日 18:35
with tags
数位DP
, 674 阅读
题意：
You are given four integers A , B , C , D , there are many different (a,b,c,d) satisfy a+c>b+d && a+d≥b+c && 0≤a≤A && 0≤b≤B && 0≤c≤C && 0≤d≤D ?
做法：
可以将四个数都拆成2进制，用记忆化搜索来统计。记w1=a+c-b-d,w2=a+d-b-c,如果搜的过程中w1大于2其实可以把它变成2，对答案不影响，如果w1小于2则直接剪枝。w2也同理。
（比赛的时候完全没想到数位dp，看了huanzhizun的博客才会做）I good vegetable！a ！
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int N=64,mo=1e9+7;ll A,B,C,D;int a[N],b[N],c[N],d[N];int f[N][2][2][2][2][5][5];void add(int &x,int y){ x=(x+y)%mo;}void cg(ll x,int *a){ for (int i=0;i<N;i++) a[i]=0; int cnt=0; while(x) a[++cnt]=x%2,x/=2;}int dfs(int pos,bool u1,bool u2,bool u3,bool u4,int w1,int w2){ if (pos==0) return w1>0&&w2>=0; int ret=f[pos][u1][u2][u3][u4][w1+2][w2+2]; if (ret!=-1) return ret; ret=0; int d1=1,d2=1,d3=1,d4=1; if (u1) d1=a[pos]; if (u2) d2=b[pos]; if (u3) d3=c[pos]; if (u4) d4=d[pos]; for (int i1=0;i1<=d1;i1++) for (int i2=0;i2<=d2;i2++) for (int i3=0;i3<=d3;i3++) for (int i4=0;i4<=d4;i4++) { int ww1=w1*2+i1+i3-i2-i4; int ww2=w2*2+i1+i4-i2-i3; if (ww1>2) ww1=2; if (ww2>2) ww2=2; if (ww1<-2) continue; if (ww2<-2) continue; bool uu1=u1,uu2=u2,uu3=u3,uu4=u4; if (i1<a[pos]) uu1=0; if (i2<b[pos]) uu2=0; if (i3<c[pos]) uu3=0; if (i4<d[pos]) uu4=0; add(ret,dfs(pos-1,uu1,uu2,uu3,uu4,ww1,ww2)); } return f[pos][u1][u2][u3][u4][w1+2][w2+2]=ret;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld",&A,&B,&C,&D); cg(A,a); cg(B,b); cg(C,c); cg(D,d); memset(f,-1,sizeof(f)); printf("%d\n",dfs(63,1,1,1,1,0,0)); }} |
评论 (0)
