UVA10564-----Paths through the Hourglass-----简单的计数DP - c++编程基础

题目意思：

给你2*n-1行

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

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

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

解题思路：

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

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

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

下面上代码：

#include  
#include  
#include  
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<=n)  
                    j++;  
            }  
            now += num[i][pos];  
        }  
        cout<