DP+高精度 （和1009是一样的题目，不过数字的位数达到了180，所以要用高精度）
同样是记忆化搜索实现，不过加入了高精度，一些细节地方就注意一下。我的代码写的不好，有点长有点乱…………
#include <cstdio> #include <cstring> #define LEN 210 //高精度数组的大小 #define MAX 210 //位数 struct num { int a[LEN],len; //a数组保存高精度 }dp[MAX][15]; //最多180位，最高进制为10 int N,K; void init() { for(int i=1; i<N; i++) for(int j=0; j<K; j++) { memset(dp[i][j].a,0,sizeof(dp[i][j].a)); dp[i][j].len=-1; } for(int i=0; i<K; i++) { dp[N][i].len=1; memset(dp[N][i].a,0,sizeof(dp[N][i].a)); dp[N][i].a[0]=1; } return ; } void add(struct num p ,struct num q , struct num *ans) { struct num tmp; if(q.len>p.len) { tmp=q; q=p; p=tmp; } int t,c=0; for(int i=0; i<p.len; i++) { t=p.a[i]+q.a[i]+c; (*ans).a[i]=t%10; c=t/10; } (*ans).len=p.len; if(c>0) { (*ans).a[p.len]=1; (*ans).len++; } return ; } void dfs(int i , int j) { if(dp[i][j].len!=-1) return ; dp[i][j].len=0; for(int k=1; k<K; k++) { dfs(i+1,k); //dp[i][j]+=dp[i+1][k] add(dp[i][j] , dp[i+1][k] , &dp[i][j]); } if(j) { dfs(i+1,0); //dp[i][j]+=dp[i+1][0]; add(dp[i][j] , dp[i+1][0] , &dp[i][j]); } return ; } void solve() { struct num ans; memset(ans.a,0,sizeof(ans.a)); ans.len=0; for(int i=1; i<K; i++) { dp[1][i].len=0; for(int j=0; j<K; j++) { dfs(2,j); //dp[1][i]+=dp[2][j] add(dp[1][i] , dp[2][j] , &dp[1][i]); } add(ans , dp[1][i] , &ans); } for(int i=ans.len-1; i>=0; i--) printf("%d",ans.a[i]); printf("\n"); } int main() { while(scanf("%d%d",&N,&K)!=EOF) { init(); solve(); } return 0; }