Paths through the Hourglass
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include <stdio.h> 2 #include <string.h> 3 4 int n,s; 5 long long dp[55][56][550]; 6 int a[56][55]; 7 8 int d(int x,int y,int m) 9 { 10 if(x>=2*n-1) 11 return 0; 12 int v=a[x][y]; 13 if(dp[x+1][y][m-v]>0) 14 { 15 printf("L"); 16 d(x+1,y,m-v); 17 } 18 else 19 { 20 printf("R"); 21 d(x+1,y+1,m-v); 22 } 23 return 0; 24 } 25 26 int main() 27 { 28 int i,j,k; 29 while(scanf("%d %d",&n,&s)!=EOF) 30 { 31 if(n==0 && s==0) 32 break; 33 memset(dp,0,sizeof(dp)); 34 for(i=1;i<=n;i++) 35 { 36 for(j=i;j<=n;j++) 37 { 38 scanf("%d",&a[i][j]); 39 } 40 } 41 for(i=n+1;i<=2*n-1;i++) 42 { 43 for(j=n;j<=i;j++) 44 { 45 scanf("%d",&a[i][j]); 46 } 47 } 48 49 for(i=n;i<=2*n-1;i++) 50 { 51 int v=a[2*n-1][i]; 52 dp[2*n-1][i][v]=1; 53 } 54 for(i=n*2-2;i>n;i--) 55 { 56 for(j=n;j<=i;j++) 57 { 58 int v=a[i][j]; 59 for(k=v;k<=s;k++) 60 { 61 dp[i][j][k]=dp[i+1][j][k-v]+dp[i+1][j+1][k-v]; 62 } 63 } 64 } 65 for(i=n;i>=1;i--) 66 { 67 for(j=i;j<=n;j++) 68 { 69 int v=a[i][j]; 70 for(k=v;k<=s;k++) 71 { 72 dp[i][j][k]=dp[i+1][j][k-v]+dp[i+1][j+1][k-v]; 73 } 74 } 75 } 76 77 long long cnt=0; 78 for(i=1;i<=n;i++) 79 { 80 cnt=cnt+dp[1][i][s]; 81 } 82 printf("%lld ",cnt); 83 for(i=1;i<=n;i++) 84 { 85 if(dp[1][i][s]>0) 86 { 87 printf("%d ",i-1); 88 d(1,i,s); 89 break; 90 } 91 } 92 printf(" "); 93 } 94 return 0; 95 }