白駿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を忘れずによく考えてから編みます.