PAT (Advanced Level) 1049. Counting Ones (30)

数位DP。dp[i][j]表示i位,最高位为j的情况下总共有多少1.

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std; long long dp[][];
char s[]; void init()
{
memset(dp,,sizeof dp); long long num=; for(int i=; i<=; i++)
{
for(int j=; j<=; j++)
{
if(j==) dp[i][j]=num;
for(int s=; s<=; s++)
dp[i][j]=dp[i][j]+dp[i-][s];
}
num=num*;
} } int main()
{
init();
while(~scanf("%s",s))
{
int len=strlen(s);
long long n=;
for(int i=; s[i]; i++) n=n*+s[i]-'';
long long ans=; for(int i=; i<s[]-''; i++) ans=ans+dp[len][i];
for(int i=; s[i]; i++)
{
int d=len-i;
for(int j=; j<s[i]-''; j++) ans=ans+dp[d][j];
}
long long x=;
for(int i=; s[i]; i++)
{
x=x*+s[i]-'';
if(s[i]=='')
{
long long tmp=x;
for(int j=i+; s[j]; j++) tmp=tmp*;
ans=ans+n-tmp+;
}
}
printf("%lld\n",ans);
}
return ;
}
上一篇:【Luogu1272】重建道路(动态规划)


下一篇:【译】Asp.net mvc 使用ITextSharp PDF to HTML (解决img标签问题)