本文主要是介绍Bomb HDU - 3555，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3555
dp[i][0]代表[i+1,n-1]位上没出现过49且第i+1位上的数不是4
dp[i][1]代表[i+1,n-1]位上没出现过49但第i+1位上的数是4
dp[i][2]代表[i+1,n-1]位上已出现过49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50;ll dp[maxn][5];
int bit[maxn];ll dfs(int pos,int sta,int limit)
{ll res;int up,i;if(pos==-1) return sta==2;if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];if(!limit) up=9;else up=bit[pos];res=0;for(i=0;i<=up;i++){if(i==4) res+=dfs(pos-1,max(sta,1),limit&&i==bit[pos]);else if(i==9) res+=dfs(pos-1,sta==1?2:sta,limit&&i==bit[pos]);else res+=dfs(pos-1,sta==2?2:0,limit&&i==bit[pos]);}if(!limit) dp[pos][sta]=res;return res;
}ll solve(ll val)
{int pos;pos=0;while(val>0){bit[pos++]=val%10;val/=10;}return dfs(pos-1,0,1);
}int main()
{ll n;int t;memset(dp,-1,sizeof(dp));scanf("%d",&t);while(t--){scanf("%lld",&n);printf("%lld\n",solve(n));}return 0;
}
其实可以反面考虑 即求不含49的数
#include <bits/stdc++.h>
using namespace std;
#define ll long longll dp[30][2];
ll num[30];ll solve(ll n);
ll dfs(int step,int pre,int sta,int lim);int main()
{ll n,sum;int t;scanf("%d",&t);while(t--){scanf("%lld",&n);printf("%lld\n",n-solve(n)+1);}return 0;
}ll solve(ll n)
{int i,p;i=0;while(n>0){num[++i]=n%10;n/=10;}memset(dp,-1,sizeof(dp));return dfs(i,0,0,1);
}ll dfs(int step,int pre,int sta,int lim)
{ll ans;int up,i;if(step==0) return 1;if(lim==0&&dp[step][sta]!=-1) return dp[step][sta];if(lim==1) up=num[step];else up=9;ans=0;for(i=0;i<=up;i++){if(pre==4&&i==9) continue;ans+=dfs(step-1,i,i==4,lim==1&&i==num[step]);}if(lim==0) dp[step][sta]=ans;return ans;
}
这篇关于Bomb HDU - 3555的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
