team2012-E1-mysol-0020
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
/* 解题报告 //
游戏里有 n 个厉害的怪物要打，有一些是精英怪，有一些是 BOSS
1. 每打死一个精英怪，会得到 1 个摸佛点数，最多积累 5 点
2. 在摸佛点数为 5 的时候打死一个 BOSS，可以得到一个宝物
3. 每个 BOSS 拥有自己的血量和攻击力，打死 BOSS 后的摸佛值会归零
玩家的属性有三个：血量、攻击力、喝一瓶药水后的回复值
每个回合的战斗按照如下的顺序，直到任意一方血量小于等于零为止
决定是否喝药 >> 我方攻击 >> 敌方攻击 >> 决定是否喝药（如果之前没喝）
玩家希望在获得尽可能多宝物的情况下，所喝药水最少
先讲讲打死每个 BOSS 所需要的药水数 gao(i) 的做法
为了避免思路混乱，我程序里用的是分类讨论：
【如果敌方攻击力小于等于我方喝药水后的回复值】
在这种情况下，最佳策略是拼命地去攻击
直到下一次攻击之前，发现一次攻击不能打死 BOSS
但 BOSS 却能一刀砍死玩家的时候，才去喝一瓶药水
这样可以最大程度地避免药水的浪费
【如果敌方攻击力大于我方喝药水后的回复值】
为了尽可能地保命，最佳策略是每次被攻击后都喝一瓶药水（后手喝药）
打了一定回合后，可能出现几种状况：
『敌人被打死了』
为了计算最少需要的药水数，可以把多喝的药吐出来
直到血量不能再低了，或者没得吐了为止
『我方如果不在攻击前喝一瓶药，则会被打死』
被迫喝一瓶药，并且以后每回合的开始阶段也必须先喝药再攻击
实际上是使用掉后手喝药转为先手喝药的一次机会（放大招）
如果以后再碰到更进一步的『即使攻击前喝了药，也会被打死』
则参考下面一节的内容
『怎么做都没救了』
放弃吧
差不多就是这样，再说说 main() 函数里的 dp 部分
dp[i] 是一个 pair<int,int>，记录的是处理完前 i 个怪物后
能打死的最多 BOSS 数是多少，并且在这种的情况下需要消耗的最少药水数是多少
然后从第一个怪处理到最后一个怪：
1. 如果第 i 个怪是精英怪，dp[i] = dp[i - 1]
2. 如果第 i 个怪是 BOSS 则往前数 5 个精英怪到第 x 个位置
dp[i] = max(dp[i - 1], {dp[x].first + 1, dp[x].second - gao(i)})
实际上就是把最近的 5 个精英怪强制保留给当前 BOSS
然后，在这些精英怪之前的位置里选一个 dp[x] 值最大的来转移
实现起来很简单，用 vector 保存精英怪的位置即可，dp 的复杂度是 O(n)
另外，由于使用的是分类讨论 + 模拟的方法去计算打 BOSS 需要喝多少药
因此我的复杂度是 O(min(BossHP / HeroAtk, HeroHP / BossAtk))
最坏情况下也差不多是 O(HP) 的，不比 dp 快，但也暂时没有找到更快的公式法
// By 猛犸也钻地 @ 2012.07.26 */
}}}
{{{
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
PII dp[50001];
int ty[50001],hp[50001],dm[50001];
int mem[1001][11],HP,DM,RC,n;
int gao(int i){
if(~mem[hp[i]][dm[i]]) return mem[hp[i]][dm[i]];
int ih=HP,eh=hp[i];
int ip=DM,ep=dm[i],ret=0;
if(ep<=RC) while(1){
eh-=ip; if(eh<=0) return mem[hp[i]][dm[i]]=ret;
if(ih<=ep) ih=min(ih+RC,HP),ret++;
ih-=ep; if(ih<=0) return mem[hp[i]][dm[i]]=-1;
}else{
bool o=true;
int use=0;
while(1){
eh-=ip; if(eh<=0) break;
if(ih<=ep){
if(!o) return mem[hp[i]][dm[i]]=-1;
o=false;
ih=min(ih+RC,HP);
ret+=++use,use=0;
}
ih-=ep; if(ih<=0) return mem[hp[i]][dm[i]]=-1;
ih+=RC; use++;
}
use-=min((ih-1)/RC,use);
ret+=use;
return mem[hp[i]][dm[i]]=ret;
}
}
int main(){
while(scanf("%d",&n)==1){
for(int i=1;i<=n;i++){
scanf("%d",ty+i);
if(ty[i]) scanf("%d%d",hp+i,dm+i);
}
scanf("%d%d%d",&HP,&DM,&RC);
vector<int> u;
memset(mem,-1,sizeof(mem));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i]=dp[i-1];
if(!ty[i]) u.push_back(i);
if(!ty[i] || u.size()<=4) continue;
PII c=dp[u[u.size()-5]-1];
int w=gao(i);
if(~w) dp[i]=max(dp[i],PII(c.first+1,c.second-w));
}
printf("%d %d\n",dp[n].first,-dp[n].second);
}
}
}}}/* 解题报告 //
游戏里有 n 个厉害的怪物要打，有一些是精英怪，有一些是 BOSS
1. 每打死一个精英怪，会得到 1 个摸佛点数，最多积累 5 点
2. 在摸佛点数为 5 的时候打死一个 BOSS，可以得到一个宝物
3. 每个 BOSS 拥有自己的血量和攻击力，打死 BOSS 后的摸佛值会归零
玩家的属性有三个：血量、攻击力、喝一瓶药水后的回复值
每个回合的战斗按照如下的顺序，直到任意一方血量小于等于零为止
决定是否喝药 >> 我方攻击 >> 敌方攻击 >> 决定是否喝药（如果之前没喝）
玩家希望在获得尽可能多宝物的情况下，所喝药水最少
先讲讲打死每个 BOSS 所需要的药水数 gao(i) 的做法
为了避免思路混乱，我程序里用的是分类讨论：
【如果敌方攻击力小于等于我方喝药水后的回复值】
在这种情况下，最佳策略是拼命地去攻击
直到下一次攻击之前，发现一次攻击不能打死 BOSS
但 BOSS 却能一刀砍死玩家的时候，才去喝一瓶药水
这样可以最大程度地避免药水的浪费
【如果敌方攻击力大于我方喝药水后的回复值】
为了尽可能地保命，最佳策略是每次被攻击后都喝一瓶药水（后手喝药）
打了一定回合后，可能出现几种状况：
『敌人被打死了』
为了计算最少需要的药水数，可以把多喝的药吐出来
直到血量不能再低了，或者没得吐了为止
『我方如果不在攻击前喝一瓶药，则会被打死』
被迫喝一瓶药，并且以后每回合的开始阶段也必须先喝药再攻击
实际上是使用掉后手喝药转为先手喝药的一次机会（放大招）
如果以后再碰到更进一步的『即使攻击前喝了药，也会被打死』
则参考下面一节的内容
『怎么做都没救了』
放弃吧
差不多就是这样，再说说 main() 函数里的 dp 部分
dp[i] 是一个 pair<int,int>，记录的是处理完前 i 个怪物后
能打死的最多 BOSS 数是多少，并且在这种的情况下需要消耗的最少药水数是多少
然后从第一个怪处理到最后一个怪：
1. 如果第 i 个怪是精英怪，dp[i] = dp[i - 1]
2. 如果第 i 个怪是 BOSS 则往前数 5 个精英怪到第 x 个位置
dp[i] = max(dp[i - 1], {dp[x].first + 1, dp[x].second - gao(i)})
实际上就是把最近的 5 个精英怪强制保留给当前 BOSS
然后，在这些精英怪之前的位置里选一个 dp[x] 值最大的来转移
实现起来很简单，用 vector 保存精英怪的位置即可，dp 的复杂度是 O(n)
另外，由于使用的是分类讨论 + 模拟的方法去计算打 BOSS 需要喝多少药
因此我的复杂度是 O(min(BossHP / HeroAtk, HeroHP / BossAtk))
最坏情况下也差不多是 O(HP) 的，不比 dp 快，但也暂时没有找到更快的公式法
// By 猛犸也钻地 @ 2012.07.26 */
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
PII dp[50001];
int ty[50001],hp[50001],dm[50001];
int mem[1001][11],HP,DM,RC,n;
int gao(int i){
if(~mem[hp[i]][dm[i]]) return mem[hp[i]][dm[i]];
int ih=HP,eh=hp[i];
int ip=DM,ep=dm[i],ret=0;
if(ep<=RC) while(1){
eh-=ip; if(eh<=0) return mem[hp[i]][dm[i]]=ret;
if(ih<=ep) ih=min(ih+RC,HP),ret++;
ih-=ep; if(ih<=0) return mem[hp[i]][dm[i]]=-1;
}else{
bool o=true;
int use=0;
while(1){
eh-=ip; if(eh<=0) break;
if(ih<=ep){
if(!o) return mem[hp[i]][dm[i]]=-1;
o=false;
ih=min(ih+RC,HP);
ret+=++use,use=0;
}
ih-=ep; if(ih<=0) return mem[hp[i]][dm[i]]=-1;
ih+=RC; use++;
}
use-=min((ih-1)/RC,use);
ret+=use;
return mem[hp[i]][dm[i]]=ret;
}
}
int main(){
while(scanf("%d",&n)==1){
for(int i=1;i<=n;i++){
scanf("%d",ty+i);
if(ty[i]) scanf("%d%d",hp+i,dm+i);
}
scanf("%d%d%d",&HP,&DM,&RC);
vector<int> u;
memset(mem,-1,sizeof(mem));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i]=dp[i-1];
if(!ty[i]) u.push_back(i);
if(!ty[i] || u.size()<=4) continue;
PII c=dp[u[u.size()-5]-1];
int w=gao(i);
if(~w) dp[i]=max(dp[i],PII(c.first+1,c.second-w));
}
printf("%d %d\n",dp[n].first,-dp[n].second);
}
}