首页 > 代码库 > UVA_10564 计数DP

UVA_10564 计数DP

2024-07-16 18:25:19   213人阅读

也是经典的计数DP题，想练练手，故意不写记忆化搜索，改成递推，还是成功了嘞。。。不过很遗憾一开始WA了，原来是因为判断结束条件写个 n或s为0，应该要一起为0的，搞的我以为自己递推写挫了，又改了一下，其实递推没问题，就是写出来不好看

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing 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;}

　　


联系
我们