本文主要是介绍hdu 3555 Bomb，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 3555 Bomb
这个题目是最初级的数位dp题目了
递推的形式：
dp1[ i ] 表示有i个自由位含有49的个数
dp2[ i ] 表示有i个自由位以9开头不含49的个数
dp3[ i ] 表示有i个自由不以9开头且不含49的个数
要注意的是递推计算的是[0 , n-1] 范围内的数,所以n要++，为什么看程序注释
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;typedef long long ll;
ll dp1[20],dp2[20],dp3[20],digit[20];
void init()
{dp3[0]=1;dp1[1]=0,dp2[1]=1,dp3[1]=9;for(int i=2;i<20;i++){dp1[i]=10*dp1[i-1]+dp2[i-1];dp2[i]=dp2[i-1]+dp3[i-1];dp3[i]=8*dp2[i-1]+9*dp3[i-1];}//cout<<dp1[2]<<" "<<dp2[2]<<" "<<dp3[2]<<endl;
}
int main()
{init();ll n;int T;scanf("%d",&T);while(T--){scanf("%I64d",&n);int tot=0;for(;n;n/=10) digit[tot++]=n%10;int last=0,flag=0;ll ans=0;for(int i=tot-1;i>=0;i--){for(int j=0;j<digit[i];j++){//if(i==0) cout<<j<<" ";ans+=dp1[i];if(flag) ans+=dp2[i]+dp3[i];else if(j==4) ans+=dp2[i];}if(last==4&&digit[i]==9) flag=1;last=digit[i]; // 当last只要一等于digit[0]的时候程序就退出了，所以没有判断n是否满足条件// if(i==1) cout<<flag<<endl;}printf("%I64d\n",ans);}return 0;
}
还有就是记忆化搜索的形式实现的，有一点要注意的是dfs传递的形参一定会把完整的状态表示出来，不然没法转移
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;typedef long long ll;
ll dp[20][3];
int digit[20];ll dfs(int pos,int state,bool doing)
{if(pos<0) return state==2;if(!doing&&dp[pos][state]!=-1) return dp[pos][state];ll ans=0;int end=doing?digit[pos]:9;for(int i=0;i<=end;i++){int ns=state;if(ns==1&&i==9) ns=2;if(ns==1&&i!=4) ns=0;if(ns==0&&i==4) ns=1;ans+=dfs(pos-1,ns,doing&&i==end);}if(!doing) dp[pos][state]=ans;return ans;
}
int main()
{memset(dp,-1,sizeof(dp));ll n;int T;scanf("%d",&T);while(T--){scanf("%I64d",&n);int tot=0;for(;n;n/=10) digit[tot++]=n%10;printf("%I64d\n",dfs(tot-1,0,1));}return 0;
}
这篇关于hdu 3555 Bomb的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
