白駿11057上り坂

質問する

質問リンク:https://www.acmicpc.net/problem/11057

ポリシー

の数字をゼロで始めることができます.これは大きなヒントです.

隣接数は

以上であるべきである.

注記分解は、

dp[現在の数][残りの数]で行います.

コード#コード#

#include<bits/stdc++.h>

using namespace std;

#define mine

int N;
int dp[11][1002];
const int MOD = 10007;
int incNum(int n, int c){
    if(c <= 0) return 0;
    /// 숫자가 하나 남았을 때는 자명하므로 미리 선언해준다. 
    if(c == 1) return dp[n][1];
    int& ret = dp[n][c];
    if(ret != -1) return ret;
    ret = 0;
    // 다음재귀에서 사용할 수 있는 모든 수를 계산해준다.
    for(int i=n; i<10; i++){
        ret = (ret+incNum(i, c-1))%MOD;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    memset(dp, -1, sizeof(dp));
    // 남은수의 개수가 1일경우의 값들을 미리 초기화해준다. 
    for(int i=0; i<10; i++) dp[i][1] = 10-i;
	// 처음숫자가 0으로 시작하면 모든 수가 가능하므로 0으로 시작한다. 
    cout << incNum(0, N) << endl;

    return 0;
}

感想

dp[現在数][残数]でアルゴリズムを記述する考えがよいと思います.問題を解くときはbasecaseを忘れずによく考えてから編みます.