Paths through the Hourglass UVA - 10564 简单dp(码力)

xiaoxiao2021-02-27  166

转自: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(""); } }
转载请注明原文地址: https://www.6miu.com/read-15912.html

最新回复(0)