Bomb
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4063 Accepted Submission(s): 1403
Problem Description
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the
power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
Input
The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.
The input terminates by end of file marker.
Output
For each test case, output an integer indicating the final points of the power.
Sample Input
3 1 50 500
Sample Output
0 1 15HintFrom 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499", so the answer is 15.题意:求0-n中出现了多少个含有49的数字。小结:第一次做数位dp的题,对数位dp的一般模式有了一些了解,不过还是有很多地方没搞懂,dp的初始化,这里为什么n要++,为什么以i开始的时候,后面呢能取到所有出现49的情况等等。代码:#include<iostream> #include<vector> #include<string> #include<queue> #include<map> #include<cstdio> #include<cstring> #define maxn 2005 #define ll unsigned long long #define INF 0xfffffff using namespace std; int digit[25]; ll dp[25][3]; //dp[i][0]表示长度为i不出现49的数字个数 //dp[i][1]表示长度为i以9开头不出现49的数字个数 //dp[i][2]表示长度为i出现49的数字个数 void init() { memset(dp,0,sizeof(0)); dp[0][0]=1;//这里一开始还是不理解,不过从后面推的话是正确的 for(int i=1;i<=20;i++) { dp[i][0]=10*dp[i-1][0]-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][1]+10*dp[i-1][2]; } } int main() { int t; ll n,ans; init(); cin>>t; while(t--) { ans=0; cin>>n; n++;//不理解为什么要++ //求出n的每个数位 int cnt=0; memset(digit,0,sizeof(digit)); while(n) { digit[++cnt]=n%10; n/=10; } int flag=0;//标记是否前面出现过49 for(int i=cnt;i>=1;i--) { ans+=digit[i]*dp[i-1][2];//i-1位含有49 不理解这里有可能以digit[i]开头的,后面的所有dp[i-1][2]情况不是都取的到 if(flag) { ans+=digit[i]*dp[i-1][0];//i-1位不含有49 这里也是 } if(flag==0&&digit[i]>4) { ans+=dp[i-1][1]; } if(digit[i]==9&&digit[i+1]==4) flag=1; } cout<<ans<<endl; } return 0; }第二种做法:标准的记忆化搜索
今天大强给我讲了下划状态图,说dp的题都可以这种方法来做,一般状态图画出来的话就好些状态转移方程。这题在花状态图的时候用了四个标记变量:pos记录当前的位置,pre记录上一个位置的数字,flag记录是否出现过49,limit记录是否受限制,就是能否取到9.代码:#include<iostream> #include<cstring> #define ll __int64 using namespace std; int digit[25]; ll dp[25][10][3];//dp记录的是没有限制的情况下的状态 ll dfs(int pos,int pre,int flag,int limit) { if(pos==-1) return flag==1;//如果已经遍历完n,最后一个数字是否为含有49的数字看flag if(!limit&&dp[pos][pre][flag]!=-1) return dp[pos][pre][flag]; ll sum=0; int end=(limit?digit[pos]:9); for(int i=0;i<=end;i++) { if(pre==4&&i==9) sum+=dfs(pos-1,i,1,limit&&i==end);//受限制的条件是前面的所有位都是取最大的 else sum+=dfs(pos-1,i,flag,limit&&i==end); } if(!limit) dp[pos][pre][flag]=sum; return sum; } ll work(ll n) { int cnt=0; while(n) { digit[cnt++]=n%10; n/=10; } memset(dp,-1,sizeof(dp)); ll ans=dfs(cnt-1,-1,0,1); return ans; } int main() { int t; ll n; cin>>t; while(t--) { cin>>n; cout<<work(n)<<endl; } return 0; }