URAL - 1009 简单DP..新的开始...

昨天把POJ水到300了....狐狸大牛推荐URAL....这一向就到这里做题去...( 瞻仰小媛大牛 )...

URAL的DP分类的第一题....水水更健康..这完全是递推了...没啥要比较的..直接更新...

假设现在要求长度为 N 的 K 进制数中符合条件数的总数 ( 题目意思符合条件就是N位K进制数..没有两个零相连..没有前导零 )

dp [ n ] = ( k -1 ) * ( dp [ k - 1 ] ) + ( k - 1 ) * ( dp [ k - 2 ] ) ....

这么理解..就是说N位可以在所有N-1位的基础上前面添加一位不为零的也就是 ( k-1 )个可添加的数..再加上 ( N - 1 ) 位为 0 的...也就是( k - 1 ) * ( dp [ k - 2 ] )个...

初始化..dp[ 1 ] = k -1 ( 除0不行所以是 k-1 个 ) dp[2] = k*(k-1)

#include<iostream>
#include<stdio.h>
using namespace std;
long long dp[21];
int n,k,i;
int main()
{
    while(~scanf("%d%d",&n,&k))
    {     
         dp[1]=k-1; dp[2]=(k-1)*k;
         for (i=3;i<=n;i++)
            dp[i]=(k-1)*(dp[i-1]+dp[i-2]);
         printf("%lld\n",dp[n]);                         
    }
    return 0;   
}