UVA10564-----Paths through the Hourglass-----简单的计数DP

题目意思：

给你2*n-1行

第一行有n个，第n行有1个，然后第2*n-1行有n个，一个沙漏状

里面每个单元都有一个数字

给你S，问你从顶走到底，和为S有多少种，并输出其中字典序最小的路径

解题思路：

设dp[i][j][k] 表示从下往上的满足条件的i行j列和为K的种数，这里要用long long

令tag数组表示是往左还是往右

简单的递推一下就可以出来，另外要注意这里是从0开始编号的

下面上代码：

#include<cstdio>  
#include<iostream>  
#include<cstring>  
using namespace std;  
  
#define LL long long  
  
const int maxn = 50;  
const int maxs = 550;  
  
LL dp[maxn][maxn][maxs];  
bool tag[maxn][maxn][maxs][2];  
int num[maxn][maxn];  
int n,s;  
  
int main()  
{  
    while(~scanf("%d%d",&n,&s) && n+s)  
    {  
        for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=n-i+1;j++)  
                scanf("%d",&num[i][j]);  
        }  
  
        for(int i=n+1;i<=2*n-1;i++)  
        {  
            for(int j=1;j<=i-n+1;j++)  
                scanf("%d",&num[i][j]);  
        }  
  
        memset(dp,0,sizeof(dp));  
        memset(tag,false,sizeof(tag));  
  
        //初始化  
        for(int i=1;i<=n;i++)  
        {  
            int tmp = s-num[2*n-1][i];  
            dp[2*n-1][i][tmp] = 1;  
        }  
  
        //从下往上算  
        for(int i=2*n-2;i>=n;i--)  
        {  
            for(int j=1;j<=i-n+1;j++)  
            {  
                for(int k=0;k<=s;k++)  
                {  
                    int tmp = k+num[i][j];  
                    if(dp[i+1][j][tmp] != 0 )  
                    {  
                        dp[i][j][k] += dp[i+1][j][tmp];  
                        tag[i][j][k][0] = true;  
                    }  
                    if(dp[i+1][j+1][tmp] != 0)  
                    {  
                        dp[i][j][k] += dp[i+1][j+1][tmp];  
                        tag[i][j][k][1] = true;  
                    }  
                }  
            }  
        }  
  
        for(int i=n-1;i>=1;i--)  
        {  
            for(int j=1;j<=n-i+1;j++)  
            {  
                for(int k=0;k<=s;k++)  
                {  
                    int tmp = k+num[i][j];  
                    if(dp[i+1][j-1][tmp] != 0 )  
                    {  
                        dp[i][j][k] += dp[i+1][j-1][tmp];  
                        tag[i][j][k][0] = true;  
                    }  
                    if(dp[i+1][j][tmp] != 0)  
                    {  
                        dp[i][j][k] += dp[i+1][j][tmp];  
                        tag[i][j][k][1] = true;  
                    }  
                }  
            }  
        }  
  
        int ansi = -1;  
        LL ans = 0;  
  
        for(int i=1;i<=n;i++)  
        {  
            if(dp[1][i][0] !=0 && ansi == -1)  
                ansi = i;  
            ans += dp[1][i][0];  
        }  
        cout<<ans<<endl;  
        if(ans == 0)  
        {  
            cout<<endl;  
            continue;  
        }  
  
        cout<<ansi-1<<" "; //从0开始编号  
        int j = ansi;  
        int now = 0;  
        for(int i=1;i<=2*n-1;i++)  
        {  
            int pos = j;  
            if(tag[i][pos][now][0])  
            {  
                cout<<"L";  
                if(i<n)  
                    j--;  
            }  
            else if(tag[i][pos][now][1])  
            {  
                cout<<"R";  
                if(i>=n)  
                    j++;  
            }  
            now += num[i][pos];  
        }  
        cout<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,