NYOJ 269--VF

VF

時間限制： 1000 ms  |  記憶體限制： 65535 KB 連結： NYOJ269

題意：1～1000000000之間，各位數字之和等于給定s的數的個數。

每行給出一個數s(1 ≤ s ≤ 81)，求出1~10^9内各位數之和與s相等的數的個數。

1、隻有s=1時，10^9的系數才能為1，否則就大于10^9。

是以和為1的要單一列出來。

2、如果s!=1：定義狀态dp[i][j]為前i位各位數之和為j的情況數量：對于前i為的數字之和最大為：9*i，即每一位數字都是9。

i=1、隻有一位的數字，因為s>=1，是以最低位隻能是1-9 其中的一個數字。

i>1、假設第i位放數字k（則k隻能是0~9并且k<=s），若要使第前i位數字之和為j，那麼前i-1位隻能放j-k，由此得出動态轉移方程：d[i]][j]=d[i][j]+d[i-1][j-k] (0<=k<=j&&k<=9)。

<span style="font-size:12px;color:#333333;">/**************
Author:jiabeimuwei
Times:0ms
Sources:NYOJ-269
**************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
using namespace std;
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
#define malloc(sb) (sb *)malloc(sizeof(sb))
//int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
int dp[11][81];
int main()
{
    int n,c;
    for(int i=1; i<=9; i++)
        dp[1][i]=1;
    for(int i=1; i<=9; i++)
    {
        c=9*i;
        for(int j=1; j<=c; j++)
            for(int k=0; k<=9 && k<=j; k++)
                dp[i][j]+=dp[i-1][j-k];
    }//假設第i位放數字k（則k隻能是0~9并且k<=s），若要使第前i位數字之和為j，那麼前i-1位隻能放j-k.
    while(~scanf("%d",&n))
    {
        int sum=0;
        if(n==1)
        {
            printf("10\n");
            continue;
        }
        for(int i=1; i<=9; i++)
            sum+=dp[i][n];
        printf("%d\n",sum);
    }
}</span>