简单数位dp-hdu-4734-F(x)
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4734
题目大意：
给一个数A (十进制表示形式为AnAn-1An-2 ... A2A1，定义函数 F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1，给一个B,求B以内的i,满足F(i)<=F(A)
解题思路：
很裸的数位dp,先求出F（A)，dp[i][j]:表示有i位不超过j的有多少个。
PS：开始傻逼的用dp[i][j]表示有i位前面的一共占了多少，这样的话只对特定的样例有点减枝，对所有样例没有减枝，思维转的不灵活。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#define eps 1e-6#define INF 0x3fffffff#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;int a,b;int sa[22];int bit[30],num;int lim;int Cal(int aa){ int res=0; int cnt=0; while(aa) { res+=(aa%10)*sa[cnt]; //求F(A) cnt++; aa/=10; } return res;}int dp[22][11000];ll dfs(int cur,int la,int flag){ if(!cur) { if(!flag) dp[cur][la]=1; return 1; } if(dp[cur][la]!=-1&&!flag) //记忆话搜索 return dp[cur][la]; int Max=flag?bit[cur]:9; ll res=0; for(int i=0;i<=Max;i++) { if(la<i*sa[cur-1]) continue; res+=dfs(cur-1,la-i*sa[cur-1],flag&&(i==Max)); } if(!flag) dp[cur][la]=res; return res;}ll init(int x){ num=0; while(x) { bit[++num]=x%10; //分离出每一位（十进制） x/=10; } return dfs(num,lim,1);}int main(){ int t; sa[0]=1; for(int i=1;i<=10;i++) //sa[i]=2^i sa[i]=sa[i-1]*2; scanf("%d",&t); memset(dp,-1,sizeof(dp)); for(int ca=1;ca<=t;ca++) { scanf("%d%d",&a,&b); lim=Cal(a); //求出F(A) printf("Case #%d: %d\n",ca,init(b)); } return 0;}