hdu 3555数位dp基础入门题

#include<stdio.h>

#define N 20

long long dp[N][3];

void init(){

long long i;

dp[0][0]=1;

for(i=1;i<=20;i++) {

dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//没有考虑前导零的情况

dp[i][1]=dp[i-1][0];

dp[i][2]=dp[i-1][2]*10+dp[i-1][1];

}

}

long long slove(long long x) {

long long i,a[N],k,flag=0;

long long j;

k=0;

while(x) {

a[++k]=x%10;

x/=10;

}

a[k+1]=0;

j=0;

for(i=k;i>=1;i--) {

j=j+a[i]*dp[i-1][2];

if(flag)j=j+a[i]*dp[i-1][0];

else

if(a[i]>4)j=j+dp[i-1][1];

if(a[i+1]==4&&a[i]==9) flag=1;

}

return j;

}

int main() {

long long n,t;

init();

scanf("%I64d",&t);

while(t--) {

scanf("%I64d",&n);

printf("%I64d\n",slove(n+1));//必须加一，因为如果是n的话他只能枚举到n-1

}

return 0;

}

巴特西

hdu 3555数位dp基础入门题

最新文章

热门文章