Ural 1353 Milliard Vasya's Function（DP）-白红宇

Ural 1353 Milliard Vasya's Function（DP）

阅读量：7217 次

发布时间：2019-06-29

本文共 759 字，大约阅读时间需要 2 分钟。

题目地址:

定义dp[i][j]。表示当前位数为i位时，各位数和为j的个数。

对于第i位数来说。总能够看成在前i-1位后面加上一个0~9。所以状态转移方程就非常easy出来了:

dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i][j-2]+.......+dp[i][j-9]；

最后统计就可以。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;const int INF=0x3f3f3f3f;#define LL long longint dp[10][90];int main(){ int n, i, j, sum, s, k; memset(dp,0,sizeof(dp)); for(i=1;i<=9;i++) dp[1][i]=1; for(i=2;i<=9;i++) { s=0; for(j=1;j<=81;j++) { for(k=0;k
                
                 <=9;k++) { dp[i][j]+=dp[i-1][j-k]; } } } while(scanf("%d",&n)!=EOF) { if(n==1) { puts("10"); continue ; } sum=0; for(i=1;i<=9;i++) { sum+=dp[i][n]; } printf("%d\n",sum); } return 0;}