/* 抄watashi 他太无敌了 状态表示得很好 写得很好!!!!!
题意:要救公主,但要一关一关过去 人初始有 h , s , p , m值 每一关可以 攻击D 或 睡眠E 敌人 D : 需要 s >= s[i] 攻击后 h - = max(2s[i] - s , 0) , s++ E : 需要 m >= m[i] , p >= p[i] 睡眠后 m -= m[i] , p++ h = 0 时死掉
要注意到,前面i次用了j次攻击D的话 , 肯定有 i - j 次睡眠E 而且每D一次 s++ , 每E一次 p++ 所以用 dp[i,j,k] 记录前面搞定i个敌人 用了j次攻击,剩余k个魔法 的最大血量 当为j时,显然s = s0 + j , p = p0 + (i-j)
这样子用3维就能表示出了 其余的可以推出的 Orz
"转移的时候要注意可干性和可睡性的判断。" ^_^ */ #include<cstdio> #include<cstring> #include<algorithm>
using namespace std;
const int MAXN = 52;
int dp[MAXN][MAXN][MAXN]; char pre[MAXN][MAXN][MAXN];
int s[MAXN] , p[MAXN] , m[MAXN];
int main() {
// freopen("in","r",stdin);
int n , h , pp , ss ,mm; char ans[100];
while( ~scanf("%d%d%d%d%d" , &n ,& h ,&ss ,&pp , &mm) ) {
for(int i = 0 ; i <= n ; i++) for(int j = 0 ; j <= n ; j++) for(int k = 0 ; k <= mm ; k++) { dp[i][j][k] = 0; }
for(int i = 0 ; i < n; i++) { scanf("%d%d%d",&s[i],&p[i],&m[i]); } dp[0][0][mm] = h; for(int i = 0 ; i < n ; i++) for(int j = 0; j <= i ;j++) for(int k = 0; k <= mm ; k++) { if(dp[i][j][k] == 0)continue;
//D : h - max(2si-s,0) , s++ | s>=si //E : m - mi , p++ | p >= pi , m >= mi
int t = 2*s[i] - (ss+j); if(t < 0) t = 0; if(ss+j >= s[i] && dp[i+1][j+1][k] < dp[i][j][k] - t) { dp[i+1][j+1][k] = dp[i][j][k] - t; pre[i+1][j+1][k] = 'D'; }
t = pp + (i-j); if(t >= p[i] && k >= m[i] && dp[i+1][j][k-m[i]] < dp[i][j][k]) { dp[i+1][j][k-m[i]] = dp[i][j][k]; pre[i+1][j][k-m[i]] = 'E'; } }
int J = -1 , K; for(int j = 0 ; j <= n && J == -1 ; j ++) for(int k = 0; k <= mm ; k++) { if(dp[n][j][k]) { J = j ; K = k; break; } } if(J == -1)puts("UNLUCKY"); else { ans[n] = 0; for(int i = n-1 ; i >= 0; i--) { ans[i] = pre[i+1][J][K]; if(ans[i] == 'D') J--; else K += m[i]; } puts(ans); } } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|