2017百度之星資格賽 1003 度度熊與邪惡大魔王

本題我們可以類比背包 

背包dp[i][j] 表示再有i個物品下j個空間所獲得的最大價值

本題dp[i][j] 可以表示幹掉i個血量j個防禦力下的最小花費

我們看其實我們就是在不同血量之間轉移

如果目前技能的攻擊力 > 目前防禦力 

如果攻擊力能幹掉怪物那麼dp[i][j] = min(花費,dp[i][j]);

如果幹不掉 dp[i][j] = min(dp[i-傷害] [ j]+花費 , dp[i][j]);也就是在幹掉i-傷害值下的花費 再加使用這次技能的花費

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
ll n,m,k[1010],p[1010],a[maxn],b[maxn];
ll dp[1010][15];

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		ll ml=0,mf=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i]>>b[i];
			ml = max(ml,a[i]);
			mf = max(mf,b[i]);
		}
		ll ma=0;
		for(int i=1;i<=m;i++)
		{
			cin>>k[i]>>p[i];
			ma = max(p[i],ma);
		}
		memset(dp,0,sizeof(dp));
		if(ma<=mf){
			puts("-1");
			continue;
		}
		for(int j=1;j<=ml;j++)
		{
			for(int i=0;i<=10;i++)
			{
				dp[j][i] = inf;
				for(int u=1;u<=m;u++)
				{
					ll h = p[u]-i;
					//cout<<j-h<<endl;
					//system("pause");
					if(h<=0)continue;//傷害值小于防禦值
					if(h>=j)//可以幹掉
						dp[j][i] = min(dp[j][i],k[u]);
					else 
						dp[j][i] = min(dp[j][i],dp[j-h][i]+k[u]); 
				}
			}
		}
		ll ans=0;
		for(int i=1;i<=n;i++)
		{
			ans+=dp[a[i]][b[i]];
		}
		printf("%lld\n",ans);
	}
	return 0;
}