Uva(10564)(Paths through the Hou

链接：https://vjudge.net/problem/UVA-10564
思路：dp题，有点像数字三角形，但是因为要涉及路径输出我们不能把它拆为两个来做，还是直接记忆式搜索吧，以n为边界，上下采取不同的状态转移方程。。记住记忆式搜索不要用dp数组的值是否为0来判断是否查询过，因为本题很多点都为0（表示无解），养成好习惯用vis来判重，我就是这种不好习惯导致这道题一开始tl了。然后枚举第一排所有起点，第一个找到的解一定是题目要求最优的！
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
int a[51][51];
long long dp[51][51][501];
int vis[51][51][501];
int n,s,cnt,id;
string ress;

long long dfs(int i,int j,int k,string path){
if(dp[i][j][k]||vis[i][j][k])return dp[i][j][k];
vis[i][j][k] = 1;
if(k<0||i>2*n)return 0;
if(i==2*n&&k==0){
    if(id==-1)id=cnt,ress = path;
    return 1;
}
long long &sum = dp[i][j][k];
//上半区的状态转移
if(i<n){
    if(a[i+1][j-1]!=-1)sum+=dfs(i+1,j-1,k-a[i][j],path+'L');
    if(a[i+1][j]!=-1)sum+=dfs(i+1,j,k-a[i][j],path+'R');
}
//下半区的状态转移
else {
    if(i+1==2*n)sum+=dfs(i+1,j,k-a[i][j],path);//需要单独判断
 else if(a[i+1][j]!=-1)sum+=dfs(i+1,j,k-a[i][j],path+'L');
   if(a[i+1][j+1]!=-1)sum+=dfs(i+1,j+1,k-a[i][j],path+'R');
}
return sum;
}

int main(){
    while(~scanf("%d%d",&n,&s)&&(n||s)){
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        memset(a,-1,sizeof(a));
        ress = "";
//一定要注意输入的数据在数组中的位置！！！
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=n+1;i<2*n;i++){
        for(int j=1;j<=i-n+1;j++){
            scanf("%d",&a[i][j]);
        }
    }
    long long res = 0;
    cnt = 0;
    id = -1;
    for(int j=1;j<=n;j++,cnt++){
        res+=dfs(1,j,s,"");
    }
        if(res)printf("%lld\n%d %s\n",res,id,ress.c_str());
    else printf("0\n\n");
}
    return 0;
}