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;  
}