zoj 3369 Saving Princess

zoj 3369 Saving Princess

#include<cstdio>#include<iostream>#include<cstring>using namespace std;struct Mon { int s, p, m;} a[100];int f[55][55][55];char me[55][55][55];int backt[55][55][55];int backm[55][55][55];int n, h0, s0, p0, m0;char ans[55];void dp() { f[0][0][m0] = h0; for(int i=0; i<n; i++) { for(int t=0; t<=i; t++) { for(int m=0; m<=m0; m++) { if(f[i][t][m] != -1) { int s = s0 + t; int p = p0 + i - t; if(s >= a[i+1].s && f[i][t][m] - max(2*a[i+1].s - s, 0) > 0) { if(f[i+1][t+1][m] < f[i][t][m] - max(2*a[i+1].s - s, 0)) { f[i+1][t+1][m] = f[i][t][m] - max(2*a[i+1].s - s, 0); me[i+1][t+1][m] = 'D'; backt[i+1][t+1][m] = t; backm[i+1][t+1][m] = m; } } if(p >= a[i+1].p && m >= a[i+1].m) { if(f[i+1][t][m-a[i+1].m] < f[i][t][m]) { f[i+1][t][m-a[i+1].m] = f[i][t][m]; me[i+1][t][m-a[i+1].m] = 'E'; backt[i+1][t][m-a[i+1].m] = t; backm[i+1][t][m-a[i+1].m] = m; } } } } } }}int main(){ while(scanf("%d%d%d%d%d", &n, &h0, &s0, &p0, &m0) == 5) { memset(f, -1, sizeof(f)); for(int i=1; i<=n; i++) { scanf("%d%d%d", &a[i].s, &a[i].p, &a[i].m); } dp(); memset(ans, 0, sizeof(ans)); int flag = 0; for(int i=0; i<=n; i++) { for(int m=0; m<=m0; m++) { if(f[n][i][m] != -1) { flag = 1; for(int j=n-1; j>=0; j--) { ans[j] = me[j+1][i][m]; if(j == 0) break; int t = backt[j+1][i][m]; m = backm[j+1][i][m]; i = t; } break; } } if(flag) break; } if(flag == 0) printf("UNLUCKYn"); else printf("%sn", ans); } return 0;}