2156-Magic Slayer

問題概要

あなたは魔法を使ってモンスターを倒す魔法使いである．

モンスターはそれぞれHPを持っている．あなたは魔法を使ってモンスターのHPを削ることが出来る．
魔法の範囲は一体か，全ての正面に居るモンスターかの2種類があり，魔法ごとに来まっている．
モンスターはHPが0以下になると倒されたことになる．
ところで魔法は使うとMPを消費する．MPは有限なので出来るだけ消費を抑えてモンスターを倒したい．
最小のMPを求めるプログラムを書け!

解法

DP+RMQ
DPとRMQを用いて単体攻撃魔法でq以上のダメージを与える最小のMPを調べる．
そうすると全体攻撃魔法でq与えたと仮定したときの，MPの最小使用量をO(N)で求められる．
後はqを全探索する．

追記：RMQを使わなくても，線形時間の前処理で"q以上のダメージを与える最小のMP"は求められますorz

実装(C++)

RMQはSpagetthi Sourceさんのを利用しました．

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

typedef pair<int,int> P;
P all[100];
P single[100];
int allcount,singlecount;
int N,M;
int HP[100];
const int INF=99999999;
int MAX=2000000;
int *buildRMQ(int *a, int n) {
	int logn = 1;
	for (int k = 1; k < n; k *= 2) ++logn;
	int *r = new int[n * logn];
	int *b = r; copy(a, a+n, b);
	for (int k = 1; k < n; k *= 2) {
		copy(b, b+n, b+n); b += n;
		for(int i=0;i<n-k;i++) b[i] = min(b[i], b[i+k]);
	}
	return r;
}
int minimum(int x, int y, int *rmq, int n) {
	int z = y - x, k = 0, e = 1, s; // y - x >= e = 2^k なる最大 k
	s = ( (z & 0xffff0000) != 0 ) << 4; z >>= s; e <<= s; k |= s;
	s = ( (z & 0x0000ff00) != 0 ) << 3; z >>= s; e <<= s; k |= s;
	s = ( (z & 0x000000f0) != 0 ) << 2; z >>= s; e <<= s; k |= s;
	s = ( (z & 0x0000000c) != 0 ) << 1; z >>= s; e <<= s; k |= s;
	s = ( (z & 0x00000002) != 0 ) << 0; z >>= s; e <<= s; k |= s;
	return min( rmq[x+n*k], rmq[y+n*k-e+1] );
}
int sdamage[2000001];
int alldamage[2000001];
int main() {
	while(1){
		cin>>N;
		if(N==0)break;
		MAX=0;
		for(int i=0;i<N;i++){
			cin>>HP[i];
			MAX=max(MAX,HP[i]);
		}
		allcount=singlecount=0;
		cin>>M;
		bool NA=false;
		for(int i=0;i<M;i++){
			string t1,t2;
			int a,b;
			cin>>t1>>a>>t2>>b;
			MAX=max(MAX,b);
			if(b==0)continue;
			if(t2=="All"){
				all[allcount++]=(P(a,b));
			}else{
				single[singlecount++]=(P(a,b));
			}
			if(a==0&&b>0){
				NA=true;
			}
		}
		if(NA){
			cout<<"0"<<endl;
			continue;
		}
		MAX*=2;
		for(int i=0;i<=MAX;i++)sdamage[i]=alldamage[i]=INF;

		alldamage[0]=sdamage[0]=0;

		for(int j=0;j<allcount;j++){
			for(int i=0;i<=MAX;i++){
				if(i-all[j].second>=0&&alldamage[i-all[j].second]<INF){
					alldamage[i]=min(alldamage[i],alldamage[i-all[j].second]+all[j].first);
				}
			}
		}
		for(int j=0;j<singlecount;j++){
			for(int i=0;i<=MAX;i++){
				if(i-single[j].second>=0&&sdamage[i-single[j].second]<INF){
					sdamage[i]=min(sdamage[i],sdamage[i-single[j].second]+single[j].first);
				}
			}
		}
		int *rmq=buildRMQ(sdamage,MAX+1);
		int ans=INF;
		int minMP=INF;
		for(int i=MAX/2;i>=0;i--){
			int pans;
			if(alldamage[i]<INF){
				if(alldamage[i]>=minMP)continue;
				minMP=alldamage[i];
				pans=alldamage[i];
				for(int j=0;j<N;j++){
					if(HP[j]-i<=0)continue;
					pans+=minimum(HP[j]-i,MAX,rmq,MAX+1);
					if(pans>INF)break;
				}
				ans=min(pans,ans);
			}
		}
		int pans=INF;
		for(int i=MAX/2;i<=MAX;i++){
			pans=min(pans,alldamage[i]);
		}
		ans=min(ans,pans);
		cout<<ans<<endl;
		delete[] rmq;
	}
	return 0;
}