ZOJ3369

Saving Princess

Description

Saving princesses is always a hard work. Ivan D’Ourack is planning to save the princess locked in the tower. However, n dangerous monsters are guarding the road from the city where Ivan lives to the tower where the princess is locked.

Fortunately Ivan is a warrior and a magician. Thus he can defeat monsters in a fight, and enchant them to pass unnoticed.

Initially Ivan has h health points, strength s, spell power p and m mana points. To defeat i-th monster in a fight, he must have strength at least si, and he loses max(2si - s, 0) health points in a fight. If the number of health points becomes 0 or less, Ivan dies. After defeating a monster Ivan’s strength increases by 1.

To enchant i-th monster Ivan must have spell power at least pi and he spends mi mana points to do it. If Ivan does not have mi mana points, he cannot enchant the monster. After enchanting the monster Ivan’s spell power increases by 1.

Find out, whether Ivan can save princess, and if he can how to do it.

Input

The first line of the input file contains n, h, s, p and m (1 ≤ n ≤ 50, 1 ≤ h ≤ 50, 0 ≤ s, p, m ≤ 50). The following n lines contain three integer numbers each — si, pi, and mi (1 ≤ si, pi, mi ≤ 50).

There are multiple cases. Process to the end of file.

Output

If Ivan cannot save princess, output “UNLUCKY”. In the other case output n characters, the i-th character must be ’D’ if Ivan must defeat the i-the monster, or ‘E’ if he must enchant it.

Sample Input

3 12 5 5 6
5 5 2
6 5 2
6 7 3
3 11 5 5 6
5 5 2
6 5 2
6 7 3

Sample Output

DED
UNLUCKY

最好想的就是裸搜了 但是最差情况是2⁵⁰ 明显超时 注意到数据范围 50*50*50*50 明显比2⁵⁰要小，而且具有不重复性。所以需要数组保存状态，也可以理解为dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef  long long LL;

#define clr(x) memset((x),0,sizeof(x))
#define inf 0x3f3f3f3f
using namespace  std;
bool dp[55][110][55][55];
int s[55];
int p[55];
int m[55];
char ans[55];
int flag ;
int  n,_h,_s,_p,_m;
void dfs(int i,int _h,int _s,int _p,int _m)
{
    if(dp[_h][_s][_p][_m]!=0||flag) return ;
    if(i>n)
    {
        flag = 1;
        return ;
    }
    int lost_hp = max(0,2*s[i]-_s);
    if(_s>=s[i]&&_h-lost_hp>0)
    {
        ans[i] = 'D';
        dfs(i+1,_h-lost_hp,_s+1,_p,_m);
        dp[_h-lost_hp][_s+1][_p][_m]=1;
    }
    if(flag ) return ;
    if(_p>=p[i]&&_m>=m[i])
    {
        ans[i] = 'E';
        dfs(i+1,_h,_s,_p+1,_m-m[i]);
        dp[_h][_s][_p+1][_m-m[i]]=1;
    }

}

int main()
{
    while(~scanf("%d%d%d%d%d",&n,&_h,&_s,&_p,&_m))
    {
        flag = 0;
        for(int i = 1;i<=n;i++)
        {
            scanf("%d%d%d",&s[i],&p[i],&m[i]);
        }
        memset(dp,0,sizeof dp);
        dfs(1,_h,_s,_p,_m);
        if(flag){
            for(int i = 1;i<=n;i++)
                putchar(ans[i]);
        printf("\n");
        }
               if(!flag)
         puts("UNLUCKY");

    }
    return 0;
}