转自:http://www.bubuko.com/infodetail-1027838.html
自己的代码太丑了。
然后看别人的代码很简洁。。
其实对于每一行的头和尾的处理可以用 if(I>1)来处理。。之前做过。。
还有，就是状态转移，，我的一些地方错了。。因为是有些是直着上去的，，并不是真的就只是左右。。
对于输出路径；
看这里的方法，，直接就利用dp数组
然后递归输出
还有注意他这里的dp的状态，，
就是他的定义和我的有些不同。
也确实，，反正都是枚举k了。。
不必要一定要让 k的位置一定是从a[I][j]开始。。dp[I][j][k] 中 k可以是包含自己的值的状态。
可怕的是不知道为什么交上去WA了的。。
然后想了想，原来是我唯一改的地方错了，，就是要注意是左先，再到右
#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a));
#define inf 0x3f3f3f3f
#define INF 1e9
#define N 10005
#define M 305
#define bug1 printf("bug1\n");
#define bug2 printf("bug2\n");
#define bug3 printf("bug3\n");
#define LL long long
int n,S;
LL dp[45][25][505];
int a[45][25];
void print(int x,int y,int sum){
if(x>=2*n-1)return;
int t=a[x][y];
if(x<n){
if(y>1&&dp[x+1][y-1][sum-t]){//一开始写反了，所以错了
pf("L");print(x+1,y-1,sum-t);
}
else{
pf("R");print(x+1,y,sum-t);
}
}
else if(x>=n){
if(dp[x+1][y][sum-t]){
pf("L");print(x+1,y,sum-t);
}
else{
pf("R");print(x+1,y+1,sum-t);
}
}
}
int main(){
while(~sf("%d%d",&n,&S)&&n+S){
mem(dp,0);
for(int i=1;i<=n;++i){
for(int j=1;j<=n-i+1;++j){
sf("%d",&a[i][j]);
}
}
for(int i=n+1;i<=2*n-1;++i){
for(int j=1;j<=i-n+1;++j){
sf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;++i){
int t=a[2*n-1][i];
dp[2*n-1][i][t]=1;
}
for(int i=2*n-2;i>=n;--i){
for(int j=1;j<=i-n+1;++j){
int t=a[i][j];
for(int k=t;k<=S;++k){
dp[i][j][k]=dp[i+1][j][k-t]+dp[i+1][j+1][k-t];
}
}
}
LL cnt=0;
for(int i=n-1;i>=1;i--){
for(int j=1;j<=n-i+1;++j){
int t=a[i][j];
for(int k=t;k<=S;++k){
if(j>1)dp[i][j][k]+=dp[i+1][j-1][k-t];//这种用法
if(j<n-i+1)dp[i][j][k]+=dp[i+1][j][k-t];//时刻注意漏斗上边和下边的不同情况讨论
}
if(i==1)cnt+=dp[i][j][S];
}
}
pf("%lld\n",cnt);
for(int i=1;i<=n;++i){
if(dp[1][i][S]){
pf("%d ",i-1);
int t=a[1][i];
print(1,i,S);break;
}
}
puts("");
}
}
