hdu 4734 F(x) 数位dp (2013 ACM/ICPC Asia Regional Chengdu Online 1007)

发布时间:2016-12-7 18:38:16 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4734 F(x) 数位dp (2013 ACM/ICPC Asia Regional Chengdu Online 1007)",主要涉及到hdu 4734 F(x) 数位dp (2013 ACM/ICPC Asia Regional Chengdu Online 1007)方面的内容,对于hdu 4734 F(x) 数位dp (2013 ACM/ICPC Asia Regional Chengdu Online 1007)感兴趣的同学可以参考一下。

递归形式: #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; const int maxn=4700; int m,c[11],dp[11][maxn],n,a; char b[11]; int dfs(int pos,int s,int full)//长度为pos的数,其函数值不大于s的有多少? { //full表示是否是边界值,1表示是,0表示不是 if(pos==-1) { if(s>=0) return 1; else return 0; } if(s<0) return 0; if(!full&&dp[pos][s]!=-1) return dp[pos][s]; int en,ans=0,i; en=(full?b[n-pos-1]-'0':9); for(i=0;i<=en;i++) ans+=dfs(pos-1,s-i*c[pos],full&&(i==en)); if(!full)//不是边界,就记录,以防重复相同步骤,造成时间浪费 return dp[pos][s]=ans; return ans; } int main() { int i; for(i=0;i<11;i++) c[i]=1<<i; int T,tt=0; scanf("%d",&T); memset(dp,-1,sizeof(dp)); while(T--) { scanf("%d%s",&a,b); m=0; int x=1; while(a) { m+=(a%10)*x; x=x<<1; a=a/10; } n=strlen(b); int ans=dfs(n-1,m,1); printf("Case #%d: %d\n",++tt,ans); } return 0; } 一般形式,预处理: #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> using namespace std; int f[10][4700]; int a,b; int c[12],d[12]; int main() { int i,j,k; d[0]=1; for(i=1;i<=10;i++) d[i]=d[i-1]<<1; f[0][0]=1; for (i=1;i<=8;i++) { for (j=0;j<=4600;j++) if (f[i-1][j]>0) { for (k=0;k<10;k++) f[i][k*d[i-1]+j]+=f[i-1][j]; } } for (i=0;i<=8;i++) for (j=1;j<=4600;j++) f[i][j]+=f[i][j-1]; int T,tt=0; scanf("%d",&T); while(T--) { scanf("%d%d",&a,&b); int m=0,t,x=1; while(a) { m+=(a%10)*x; x=x<<1; a=a/10; } t=0; x=1; while(b) { c[++t]=b%10; x=x<<1; b=b/10; } int ans=0; for (i=t;i>=1;i--) { for (j=0;j<c[i];j++)//第i位数是j,剩余的数(F(a)-以求过的几位数)不大于m { int tm=m-j*d[i-1]; if(tm>=0)ans+=f[i-1][tm]; } m-=c[i]*d[i-1]; if(m<0)break; } if (m>=0)ans++;//加上F(B) printf("Case #%d: %d\n",++tt,ans); } return 0; } /* f[i][j]表示i位数,函数值小于等于j的有多少个。 d[i]=2^i; */

上一篇:Objective-C Runtime 【objc_msgSend函数】
下一篇:【黑马程序员】 Java 进制转换、位运算、逻辑运算

相关文章

相关评论