HUNNU11409(디지털 dp)

제목:
숫자 n을 제시하면 몇 자리를 대표하는지 알 수 있다. 현재 n자리의 숫자에서 높은 위치에서 낮은 위치까지 비차례로 줄어드는 수의 개수를 만족시켜야 한다.
문제풀이: 이 문제는 두 상태의 한 자릿수(필수), 다른 상태는 대응하는 자릿수의 마지막 위치의 그 수, 즉 dp[pos][num]이다. 기억으로 검색하면 다른 상태가 이전 자릿수를 저장한다. dp[pos][pre].
두 가지 방법: 추이와 귀속, 추이만 통과할 수 있고 귀속은 창고가 터지는 것을 발견(이 oj는 window 시스템 창고가 비교적 작고 hdu와 같은Roz를 사용한다)
점진적:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef __int64 lld;
const lld MOD=1000000007;
#define oo 0x3f3f3f3f
#define digit 100005
lld dp[digit][10];

void Dp()
{
    memset(dp,0,sizeof dp);
    for(int i=0;i<10;i++)
        dp[1][i]=1;
    for(int i=2;i<digit;i++)
    {
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<=j;k++)
            {
                dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
            }
        }
    }
}

lld Cnt(int n)
{
    lld ans=0;
    for(int i=0;i<10;i++)
        ans=(ans+dp[n][i])%MOD;
    return ans;
}

int main()
{
    Dp();
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%I64d
",Cnt(n));
    }
	return 0;
}

반복(기억 검색):

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef __int64 lld;
const lld MOD=1000000007;
#define oo 0x3f3f3f3f
#define digit 100005
lld dp[digit][10];
int bit[digit];

lld dfs(int pos,int pre,int f)
{
    if(pos<1) return 1;
    if(!f&&dp[pos][pre]!=-1) return dp[pos][pre];
    int last=f?bit[pos]:9;
    lld res=0;
    for(int i=0;i<=last;i++)
    {
        if(i>=pre)
            res=(res+dfs(pos-1,i,f&&i==last))%MOD;
    }
    if(!f) dp[pos][pre]=res;
    return res;
}

void GetBit()
{
    for(int i=1;i<digit;i++)
        bit[i]=9;
}

lld Cnt(int n)
{
    return dfs(n,0,1);
}

int main()
{
    int T;
    int n;
    GetBit();
    memset(dp,-1,sizeof dp);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%I64d
",Cnt(n));
    }
	return 0;
}