I think my solution is correct, but it keep WA3...
#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int maxn = 10;
const int maxhph = 100;
const int maxmph = 50;
struct state
{
state() {}
state(int vhp, int vmp, int vpos)
:hp(vhp), mp(vmp), pos(vpos) {}
int hp, mp, pos;
};
int n, hph, hpm, v, dh;
int l[maxn + 1];
int f[maxhph + 1][maxmph + 1][maxn + 1];
pair<state, int> g[maxhph + 1][maxmph + 1][maxn + 1];
queue<state> q;
inline void init()
{
int mph, nm;
cin >> n >> hph >> mph >> hpm >> nm >> v >> dh;
for (int i = 1; i <= n; ++i) cin >> l[i];
for (int i = 1; i <= hph; ++i)
for (int j = 1; j <= mph; ++j)
for (int k = 1; k <= n; ++k)
f[i][j][k] = INT_MAX;
q.push(state(hph, mph, n));
f[hph][mph][n] = hpm * nm;
}
inline int getk(int h)
{
if (h % hpm)
return h / hpm + 1;
else
return h / hpm;
}
inline void monster(state &x, const int h)
{
x.pos -= min(v, x.pos - 1);
if (x.pos == 1) x.hp -= getk(h);
}
inline void update(const state &x, const state &from, int h, int id)
{
if (x.hp <= 0 || x.mp <= 0) return;
if (h < f[x.hp][x.mp][x.pos])
{
f[x.hp][x.mp][x.pos] = h;
g[x.hp][x.mp][x.pos] = make_pair(from, id);
q.push(x);
}
}
inline string itos(int x)
{
char s[10];
sprintf(s, "%d", x);
return string(s);
}
void show(state x, int id)
{
string ans;
while (id != 0)
{
switch (id)
{
case -1:
ans = "L\n" + ans;
break;
case -2:
ans = "H\n" + ans;
break;
default:
ans = "T " + itos(id) + '\n' + ans;
break;
}
id = g[x.hp][x.mp][x.pos].second;
x = g[x.hp][x.mp][x.pos].first;
}
cout << "VICTORIOUS\n" << ans << endl;
exit(0);
}
void solve()
{
while (!q.empty())
{
state x = q.front();
int h = f[x.hp][x.mp][x.pos];
--x.mp; h -= l[x.pos];
if (h <= 0) show(q.front(), -1);
monster(x, h); update(x, q.front(), h, -1);
x = q.front();
h = f[x.hp][x.mp][x.pos];
--x.mp; x.hp = min(hph, x.hp + dh);
monster(x, h); update(x, q.front(), h, -2);
for (int i = n; i >= 1; --i)
{
x = q.front();
h = f[x.hp][x.mp][x.pos];
--x.mp; x.pos = i;
monster(x, h); update(x, q.front(), h, i);
}
q.pop();
}
cout << "DEFEATED" << endl;
}
int main()
{
init();
solve();
return 0;
}
Re: I think my solution is correct, but it keep WA3...
I had WA4 and it was 4th example test, so your WA3 might be 3rd example test given inside problem statement.