team2012-F3-sol-0020
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
题意：
游戏有n个关卡，有几个关卡有BOSS，只能在别的普通关卡拿到5个BUFF以后才能打
打的时候是一个回合制形式，给定BOSS和英雄的攻击力和血量，且英雄可以喝血瓶回复，问最多能打几个BOSS获得宝物，在这情况下最少用几个血瓶。
解法：
对于每个BOSS战的时候可以用DP预处理出 f[BOSS血量][英雄血量] 的时候需要用多少血瓶，转移的时候分三种
1，双方各砍一刀不喝血瓶
2，在BOSS砍英雄前喝
3，在BOSS砍英雄后喝
要注意英雄血量不能超过限度，且要保证英雄不死
然后就可以进行主DP，设 f[i]为一个pair 表示打到第i个BOSS关能得多少宝物和用几个血瓶，那么可以有两种选择
1，不打这个BOSS，由 f[i-1] 得到
2，打这个BOSS，由前面最近的相隔5个或以上普通关卡的BOSS关 f[j] 得到
第二种的实现可以用一个deque，每次从队首出队一个j，看j能不能转移到i，能则继续出队直到不能为止，那么最后一个j就是最近的，每次处理完后将i入队尾，是线性复杂度。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 50005, MAXHP = 1003, MAXATK = 11, INFI = 2100000000;
int lst[MAXN], hp[MAXN], dm[MAXN], f[MAXN], cost[MAXN];
int m_hp, m_dm, rec, dp[MAXHP][MAXHP][MAXATK];
void init()
{
for(int a = 1; a < MAXATK; a++)
for(int i = 0; i < MAXHP; i++)
for(int j = 0; j <= m_hp; j++)
{
int& ans = dp[i][j][a] = INFI;
if(i == 0) { ans = 0; continue; }
if(j == 0) { ans = INFI; continue; }
int hp2 = max(i - m_dm, 0);
if(hp2 == 0) { ans = 0; continue; }
//not recover
int m_hp2 = j - a;
if(m_hp2 > 0) takemin(ans, dp[hp2][m_hp2][a]);
//recover before boss attack
m_hp2 = min(j + rec, m_hp);
m_hp2 -= a;
if(m_hp2 > 0) takemin(ans, dp[hp2][m_hp2][a] + 1);
//recover after boss attack
m_hp2 = j - a;
if(m_hp2 > 0)
{
m_hp2 = min(m_hp2 + rec, m_hp);
takemin(ans, dp[hp2][m_hp2][a] + 1);
}
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
int tot = 0, tp;
for(int i=1;i<=n;i++)
{
scanf("%d", &tp);
if(tp)
{
lst[++tot] = i;
scanf("%d %d", &hp[tot], &dm[tot]);
}
}
scanf("%d %d %d", &m_hp, &m_dm, &rec);
init();
f[0] = cost[0] = 0;
deque<int> q;
q.push_back(0);
lst[0] = 0;
for(int i=1;i<=tot;i++)
{
int ok = 0, id;
while(!q.empty() && lst[i] - lst[q.front()] - q.size() >= 5)
{
ok = 1;
id = q.front();
q.pop_front();
}
f[i] = f[i-1];
cost[i] = cost[i-1];
if(ok)
{
q.push_front(id);
int tmp = dp[hp[i]][m_hp][dm[i]];
if(tmp != INFI)
{
if(takemax(f[i], f[id] + 1))
cost[i] = cost[id] + tmp;
else if(f[i] == f[id] + 1)
takemin(cost[i], cost[id] + tmp);
}
}
q.push_back(i);
}
printf("%d %d\n", f[tot], cost[tot]);
}
return 0;
}
}}}题意：
游戏有n个关卡，有几个关卡有BOSS，只能在别的普通关卡拿到5个BUFF以后才能打
打的时候是一个回合制形式，给定BOSS和英雄的攻击力和血量，且英雄可以喝血瓶回复，问最多能打几个BOSS获得宝物，在这情况下最少用几个血瓶。
解法：
对于每个BOSS战的时候可以用DP预处理出 f[BOSS血量][英雄血量] 的时候需要用多少血瓶，转移的时候分三种
1，双方各砍一刀不喝血瓶
2，在BOSS砍英雄前喝
3，在BOSS砍英雄后喝
要注意英雄血量不能超过限度，且要保证英雄不死
然后就可以进行主DP，设 f[i]为一个pair 表示打到第i个BOSS关能得多少宝物和用几个血瓶，那么可以有两种选择
1，不打这个BOSS，由 f[i-1] 得到
2，打这个BOSS，由前面最近的相隔5个或以上普通关卡的BOSS关 f[j] 得到
第二种的实现可以用一个deque，每次从队首出队一个j，看j能不能转移到i，能则继续出队直到不能为止，那么最后一个j就是最近的，每次处理完后将i入队尾，是线性复杂度。
#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 50005, MAXHP = 1003, MAXATK = 11, INFI = 2100000000;
int lst[MAXN], hp[MAXN], dm[MAXN], f[MAXN], cost[MAXN];
int m_hp, m_dm, rec, dp[MAXHP][MAXHP][MAXATK];
void init()
{
for(int a = 1; a < MAXATK; a++)
for(int i = 0; i < MAXHP; i++)
for(int j = 0; j <= m_hp; j++)
{
int& ans = dp[i][j][a] = INFI;
if(i == 0) { ans = 0; continue; }
if(j == 0) { ans = INFI; continue; }
int hp2 = max(i - m_dm, 0);
if(hp2 == 0) { ans = 0; continue; }
//not recover
int m_hp2 = j - a;
if(m_hp2 > 0) takemin(ans, dp[hp2][m_hp2][a]);
//recover before boss attack
m_hp2 = min(j + rec, m_hp);
m_hp2 -= a;
if(m_hp2 > 0) takemin(ans, dp[hp2][m_hp2][a] + 1);
//recover after boss attack
m_hp2 = j - a;
if(m_hp2 > 0)
{
m_hp2 = min(m_hp2 + rec, m_hp);
takemin(ans, dp[hp2][m_hp2][a] + 1);
}
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
int tot = 0, tp;
for(int i=1;i<=n;i++)
{
scanf("%d", &tp);
if(tp)
{
lst[++tot] = i;
scanf("%d %d", &hp[tot], &dm[tot]);
}
}
scanf("%d %d %d", &m_hp, &m_dm, &rec);
init();
f[0] = cost[0] = 0;
deque<int> q;
q.push_back(0);
lst[0] = 0;
for(int i=1;i<=tot;i++)
{
int ok = 0, id;
while(!q.empty() && lst[i] - lst[q.front()] - q.size() >= 5)
{
ok = 1;
id = q.front();
q.pop_front();
}
f[i] = f[i-1];
cost[i] = cost[i-1];
if(ok)
{
q.push_front(id);
int tmp = dp[hp[i]][m_hp][dm[i]];
if(tmp != INFI)
{
if(takemax(f[i], f[id] + 1))
cost[i] = cost[id] + tmp;
else if(f[i] == f[id] + 1)
takemin(cost[i], cost[id] + tmp);
}
}
q.push_back(i);
}
printf("%d %d\n", f[tot], cost[tot]);
}
return 0;
}