1级算法题就这样了,前途渺茫啊。。。
更新一下博客,我刚刚想套用数位dp的模板,发现用那个模板也是可以做到,而且比第二种方法简单很多
第一种方法:我现在用dp[pos][now]来表示第pos位数字为now时数字1的数量,如果用数位dp的话,现在我们有三种情况
第一种情况:now!=1,那我没什么好说的了,继续向下搜吧。
第二种情况:now==1&&limit :如果知道数位dp的套路的话,这个limit的意思相信是知道的,比如说一个数字1687,我们在程序走到pos==4,now==1时,这个时候limit==1,说明它后面的值有约束,只能从000到687,所以我们这个时候就要我们把千位的1全部加上就是688(1000也是一种)。
第三种情况:now==1&&limit==0:比如说2687,如果pos==4,now==1,这个时候limit==0,因为1_ _ _ 这里后面的三位数随便拿,反正不会超过2000就是了,这个时候把千位的1全部加起来就是pow(10,pos-1);
if(now==1) //符合第二、三种情况的话 { if(limit) //第二种情况 s+=add(pos-1); //这个函数是把后面的数字加一遍(例如上面的0到687,返回值就是688) else //第三种情况 s+=pow(10,pos-1); }
然后完整代码:
#include<iostream> #include<cstring> #include<cstring> #include<cmath> using namespace std; int dp[20][20],n,m,digit[20]; int add(int a) { if(a<=0) //比如1后面没有数字了,直接返回1 return 1; else { int count=0; for(int i=a;i>=1;i--) { count+=digit[i]*pow(10,i-1); } return count+1; //把全是0的情况也加一遍 } } int dfs(int pos,int now,int limit) { if(!pos) return 0; int num=limit?digit[pos-1]:9; int s=0; if(!limit&&dp[pos][now]!=-1) return dp[pos][now]; if(now==1) { if(limit) s+=add(pos-1); else s+=pow(10,pos-1); } for(int i=0;i<=num;i++) { s+=dfs(pos-1,i,limit&&(i==num)); } if(!limit&&dp[pos][now]==-1) dp[pos][now]=s; return s; } int cal(int a) { int len=0; while(a) { digit[++len]=a%10; a/=10; } return dfs(len+1,0,1);//在这里我把它提前了一位,这个0改成-1什么的都可以,只要不是1就行了 } int main() { cin>>n; memset(dp,-1,sizeof(dp)); cout<<cal(n)<<endl; return 0; }
第二种方法:
给我们一个数字n,求从1到n中所有数字里1的数量;这里给的分类是数位dp,那我们先用dp[i][j]来表示从1到第i位为j的数字1的数量,
例如dp[3][2]就表示从1到299的数字1的数量,那怎么推呢?
假设现在是dp[3][1],也就是从1到199,这个数字更特殊一点点,那么我们可以把它表示为两个部分,1到99和100到199,
现在1到99很简单,就是dp[2][9]就是了,那100到199呢?其实我们可以把它的百位数分离,因为它的百位一定是1,
那么就一定有10^2个1,那就变成了10^2+(1到99之间数字1的数量)。
再来一个例子dp[3][2],现在是1到299了,我们可以把它变成(1到199)+(200到299),1到199就是dp[3][1],
而200到299,因为2不是1,那么200到299等价于1到99.
于是我们可以得出一个大致的结论:
dp[3][1]= dp[3][0] + dp[2][9] +(1==1)*pow(10,3-1);
dp[3][2]= dp[3][1] + dp[2][9] +(2==1)*pow(10,3-1);
dp[i][j]= dp[i][j-1] + dp[i-1][9] +(i==1)*pow(10,i-1);
但是j==0时,j-1等于0,那么我们可以改进一下:
if(j==0)
dp[i][j]=dp[i-1][9]; dp[3][0]等价于dp[2][9]
else
dp[i][j]=dp[i][j-1]+dp[i-1][9]+(i==1)*pow(10,i-1);
终于把这个东西推完了,但是我们怎么表示一个任意的n呢?
比如说n=435,好,现在我们要求1到435之间的1的数量,435可以分为,(1到399)+(400到435)。
而400到435又可以把4分离,如果4==1(额,我是说如果这个百位上的数字为1),好吧这不可能,那就是(1到399)+(1到35)了,然后35又持续这个过程。。。,但是当n=135时,就是(1到99)+(1到35)+(35+1),最后这个(35+1)是因为百位为1,那么就要加上百位上的1,即(100到135)百位上的1有(35+1)个。直接看代码,我表达不行。
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define ll long long ll dp[15][15],ss[15],n,m; int main() { cin>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=9;i++) dp[1][i]=1; for(int i=2;i<=10;i++) { for(int j=0;j<=9;j++) { if(j==0) dp[i][j]=dp[i-1][9]; else dp[i][j]=dp[i][j-1]+dp[i-1][9]+pow((j==1)*10,i-1);//先推出 } } int digit[15]; int len=0; ll m=n; while(n) { digit[++len]=n%10;//把每一位上的数字存下来 n/=10; } for(int i=len;i>=1;i--) { ll s=pow(10,i-1);//例如1435,把435,35 ,5都存下来 ss[i]=m%s; } ll ans=0; for(int i=len;i>=1;i--) { if(i>1) ans+=dp[i][digit[i]-1]; else ans+=dp[i][digit[i]]; if(digit[i]==1&&i>1)//判断这一位是不是1, { ans+=ss[i]+1; } } cout<<ans<<endl; return 0; }