也是經典的計數DP題，想練練手，故意不寫記憶化搜索，改成遞推，還是成功了嘞。。。不過很遺憾一開始WA了，原來是因為判斷結束條件寫個 n或s為0，應該要一起為0的，搞的我以為自己遞推寫挫了，又改了一下，其實遞推沒問題，就是寫出來不好看

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define LL long long using namespace std; const int N=80; LL dp[N][N][1000]; int mat[N][N]; int p[N][N][1000]; int n,s; void print(int d,int loc,int s) {if (d==2*n-1) return;int val=mat[d][loc];if (d<n){if (dp[d+1][loc-1][s-val] && loc>1){putchar('L');print(d+1,loc-1,s-val);return;}else {putchar('R');print(d+1,loc,s-val);}}else{if (dp[d+1][loc][s-val]){putchar('L');print(d+1,loc,s-mat[d][loc]);return;}else{putchar('R');print(d+1,loc+1,s-mat[d][loc]);}} } int main() {while (scanf("%d%d",&n,&s)!=EOF){if (n==0 &&s==0) break;memset(mat,0,sizeof mat);for (int i=1;i<=2*n-1;i++){int k;if (i<=n) k=n-i+1;else k=i-n+1;for (int j=1;j<=k;j++){scanf("%d",&mat[i][j]);}}memset(dp,0,sizeof dp);for (int i=1;i<=n;i++){dp[2*n-1][i][mat[2*n-1][i]]=1;}for (int i=2*n-2;i>=1;i--){int k;if (i>=n) k=i-n+1;else k=n-i+1;if (i>=n){for (int j=1;j<=k;j++){for (int q=mat[i][j];q<=s;q++){dp[i][j][q]+=dp[i+1][j][q-mat[i][j]];dp[i][j][q]+=dp[i+1][j+1][q-mat[i][j]];}}}else{for (int j=1;j<=k;j++){for (int q=mat[i][j];q<=s;q++){dp[i][j][q]+=dp[i+1][j][q-mat[i][j]];dp[i][j][q]+=dp[i+1][j-1][q-mat[i][j]];}}}}LL ans=0;int loc=-1;for (int i=1;i<=n;i++){ans+=dp[1][i][s];if (dp[1][i][s] && loc==-1){loc=i;}}printf("%lld\n",ans);if (ans>0){printf("%d ",loc-1);print(1,loc,s);}puts("");}return 0; }

　　

轉載于:https://www.cnblogs.com/kkrisen/p/3902760.html

總結

以上是生活随笔為你收集整理的UVA 10564 计数DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。