URAL1009——DP——K-based Numbers

Description
Let’s consider 
K-based numbers, containing exactly 
N digits. We define a number to be valid if its 
K-based notation doesn’t contain two successive zeros. For example:

1010230 is a valid 7-digit number;

1000198 is not a valid number;

0001235 is not a 7-digit number, it is a 4-digit number.

Given two numbers 
N and 
K, you are to calculate an amount of valid 
K based numbers, containing 
N digits.
You may assume that 2 ≤ 
K ≤ 10; 
N ≥ 2; 
N + 
K ≤ 18.
Input
The numbers 
N and 
K in decimal notation separated by the line break.
Output
The result in decimal notation.
Sample Input
input
output

2

10

90

대의:flag과 마찬가지로 앞에 1이 있다면 현재 상태는 dp[n-1]에서 옮겨오고 앞에 0이 있다면 앞에 1이 있고 현재 상태는 dp[n-2]에서 옮겨왔다는 것을 의미한다. (0은 틀림없다) 모든 상황에 대해 (k-1)가지 방법이 있는데 처음에 0의 상태를 생각하면 틀렸다.몇 발

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int main()

{

    long long dp[200];

    int n,k;

    while(~scanf("%d%d",&n,&k)){

        dp[1] = k - 1;

        dp[2] = k*(k-1);

        for(int i = 3; i <= n ; i ++)

            dp[i] = (k-1)*(dp[i-1] + dp[i-2]);

        printf("%lld
",dp[n]);

    }

    return 0;

}