学步园

描述：dp题目，对二维数组直接输入，没有转化提交时一直wa，后来转化后，提交就正确了，状态方程dp[i][j][m]+=dp[i+1][j][m-num[i][j]]+dp[i+1][j+1][m-num[i][j]]，从下往上状态转移便于输出
#include <cstdio>
#include <cstring>
int n,m,p;
int num[50][50];
long long sum,dp[50][50][510];
int main()
{
  //  freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(!n&&!m) break;
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        for(int i=1; i<=n; ++i)
            for(int j=i; j<=n; ++j) scanf("%d",&num[i][j]);
        for(int i=n+1; i<2*n; ++i)
            for(int j=n; j<=i; ++j) scanf("%d",&num[i][j]);

//        for(int i=1;i<2*n;++i)
//        {for(int j=1;j<=2*n;++j)
//        printf("%d ",num[i][j]);puts("");} puts("");
        sum=0;p=-1;
        for(int i=n; i<2*n; ++i) dp[2*n-1][i][num[2*n-1][i]]=1;
        for(int i=2*n-2; i>=n; --i)
            for(int j=n; j<=i; ++j)
                for(int k=num[i][j]; k<=m; ++k)
                    dp[i][j][k]+=dp[i+1][j][k-num[i][j]]+dp[i+1][j+1][k-num[i][j]];
        for(int i=n-1; i>=1; --i)
            for(int j=i; j<=n; ++j)
                for(int k=num[i][j]; k<=m; ++k)
                    dp[i][j][k]+=dp[i+1][j][k-num[i][j]]+dp[i+1][j+1][k-num[i][j]];
        for(int i=1; i<=n; ++i) if(dp[1][i][m]) sum+=dp[1][i][m];
        printf("%lld\n",sum);
        if(sum!=0)
        {
            int i=1;
            for( ; i<=n; ++i) if(dp[1][i][m]) break;
            printf("%d ",i-1);
            for(int j=2; j<2*n; ++j)
                if(dp[j][i][m-num[j-1][i]])
                {
                    printf("L");
                    m-=num[j-1][i];
                }
                else
                {
                    printf("R");
                    m-=num[j-1][i];
                    ++i;
                }
        }
        puts("");
    }
    return 0;
}