首页 > 代码库 > UVA 10564 Paths through the Hourglass[DP 打印]
UVA 10564 Paths through the Hourglass[DP 打印]
| UVA - 10564 Paths through the Hourglass |
题意：
要求从第一层走到最下面一层，只能往左下或右下走
问有多少条路径之和刚好等于S？ 如果有的话，输出字典序最小的路径。
f[i][j][k]从下往上到第i层第j个和为k的方案数
上下转移不一样，分开处理
没必要判断走出沙漏
打印方案倒着找下去行了，尽量往左走
沙茶的忘注释掉文件WA好多次
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=25,M=505,INF=1e9;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,s,w[N<<1][N];ll f[N<<1][N][M];void dp(){ memset(f,0,sizeof(f)); for(int j=1;j<=n;j++) f[n+n-1][j][w[n+n-1][j]]=1; //xia for(int i=n+n-2;i>=n;i--) for(int j=1;j<=i-n+1;j++) for(int k=w[i][j];k<=s;k++) f[i][j][k]=f[i+1][j][k-w[i][j]]+f[i+1][j+1][k-w[i][j]]; //shang for(int i=n-1;i>=1;i--) for(int j=1;j<=n-i+1;j++) for(int k=w[i][j];k<=s;k++) f[i][j][k]=f[i+1][j][k-w[i][j]]+f[i+1][j-1][k-w[i][j]]; }void print(int i,int j,ll k){//printf("print %d %d %d\n",i,j,k); if(i==n+n-1) return; if(i<n){ if(j>1&&f[i+1][j-1][k-w[i][j]]){ putchar(‘L‘); print(i+1,j-1,k-w[i][j]); }else{ putchar(‘R‘); print(i+1,j,k-w[i][j]); } }else{ if(f[i+1][j][k-w[i][j]]){ putchar(‘L‘); print(i+1,j,k-w[i][j]); }else{ putchar(‘R‘); print(i+1,j+1,k-w[i][j]); } }}int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); while(scanf("%d%d",&n,&s)!=EOF&&(n||s)){ memset(w,0,sizeof(w)); for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) w[i][j]=read(); for(int i=n+1;i<=n+n-1;i++) for(int j=1;j<=i-n+1;j++) w[i][j]=read(); dp(); int p=0; ll sum=0; for(int i=n;i>=1;i--) if(f[1][i][s]){p=i;sum+=f[1][i][s];} printf("%lld\n",sum); if(p) printf("%d ",p-1),print(1,p,s); putchar(‘\n‘); }}
UVA 10564 Paths through the Hourglass[DP 打印]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。