题目链接：
数位dp...完全看大牛模版理解的。。。。
View Code 1 #include2 using namespace std; 3 __int64 dp[19][19][2000]; 4 int digit[19]; 5 6 //pos表示当前的位置,o表示支点，pre表示从最高位到pos的力矩之和，doing表示是否有上限，若无，则为9; 7 __int64 dfs(int pos,int o,int pre,bool doing){ 8 if(pos==-1){ 9 return pre==0; //已经全部组合10 }11 if(pre<0)return 0;//如果前面组合的力矩之和已经为负，则后面的必然小于0；12 //没有上限，且前面的状态已经搜过13 if(!doing&&dp[pos][o][pre]!=-1){14 return dp[pos][o][pre];15 }16 __int64 ans=0;17 int end=doing?digit[pos]:9;18 for(int i=0;i<=end;i++){19 int npre=pre; //枚举下一个状态20 npre+=(pos-o)*i; 21 ans+=dfs(pos-1,o,npre,doing&&i==end);22 }23 if(!doing){24 dp[pos][o][pre]=ans;25 }26 return ans;27 }28 29 __int64 solve(__int64 n){30 int pos=0;31 while(n){32 digit[pos++]=n%10;33 n/=10;34 }35 __int64 ans=0;36 for(int o=0;o
题目链接：
View Code 1 #include2 using namespace std; 3 __int64 dp[20][3]; 4 int digit[20]; 5 6 //have==1表示前一位为4,have==0表示没有出现49，have==2表示前面有49出现 7 __int64 dfs(int pos,int have,bool doing){ 8 if(pos==-1){ 9 return have==2;//找到一个解10 }11 if(!doing&&dp[pos][have]!=-1){12 return dp[pos][have];13 }14 __int64 ans=0;15 int end=doing?digit[pos]:9;16 for(int i=0;i<=end;i++){17 int nhave=have;18 if(have==1&&i!=4){19 nhave=0;20 }21 if(have==0&&i==4){22 nhave=1;23 }24 if(have==1&&i==9){25 nhave=2;26 }27 ans+=dfs(pos-1,nhave,doing&&i==end);28 }29 if(!doing)30 dp[pos][have]=ans;31 return ans;32 }33 34 __int64 solve(__int64 n){35 int pos=0;36 while(n){37 digit[pos++]=n%10;38 n/=10;39 }40 return dfs(pos-1,0,1);41 }42 43 int main(){44 int _case;45 scanf("%d",&_case);46 memset(dp,-1,sizeof(dp));47 while(_case--){48 __int64 n;49 scanf("%I64d",&n);50 printf("%I64d\n",solve(n));51 }52 return 0;53 }
昨天做的fzu的月赛。。。当时没过。。。
这个代码我没提交过。。。
View Code 1 #include2 #include 3 using namespace std; 4 __int64 dp[20][20]; 5 int digit[20]; 6 7 __int64 DFS(int pos,int have,bool doing){ 8 if(pos==-1){ 9 return have;10 }11 if(!doing&&dp[pos][have]!=-1){12 return dp[pos][have];13 }14 __int64 ans=0;15 int end=doing?digit[pos]:9;16 for(int i=0;i<=end;i++){17 int nhave=have;18 if(i==1)nhave=have+1;19 ans+=DFS(pos-1,nhave,doing&&i==end);20 }21 if(!doing){22 dp[pos][have]=ans;23 }24 return ans;25 }26 27 28 __int64 solve(__int64 n){29 int pos=0;30 while(n){31 digit[pos++]=n%10;32 n/=10;33 }34 return DFS(pos-1,0,1);35 }36 37 int main(){ 38 __int64 n,m;39 memset(dp,-1,sizeof(dp));40 while(~scanf("%I64d%I64d",&n,&m)){41 printf("%I64d\n",solve(m)-solve(n-1));42 }43 return 0;44 }45 46
PS:记忆化搜索真的很强大啊。。。