D - 度度熊与邪恶大魔王

​ HDU - 6082

思路：

​ 数据很水， 1000 ∗ 1000 ∗ 10 1000*1000*10 1000∗1000∗10的复杂度，多组输入都能过。

​ d p [ f ] [ h ] dp[f][h] dp[f][h] 表示防御力为 f f f 血量为 h h h被消灭所需的最小晶石数量。那么假设第 i i i个技能造成的伤害为 K [ i ] K[i] K[i],晶石数量为 P [ i ] P[i] P[i]

d p [ f ] [ h ] = m i n ( d p [ f ] [ h + f − K [ i ] ] + P [ i ] ) , i ∈ [ 1 , m ] & & K [ i ] > f ​ dp[f][h]=min(dp[f][h+f-K[i]]+P[i]),i \in[1,m] \&\&K[i]>f​ dp[f][h]=min(dp[f][h+f−K[i]]+P[i]),i∈[1,m]&&K[i]>f​ 。 且 d p [ f ] [ 0 ] = 0 ​ dp[f][0]=0​ dp[f][0]=0​

注意： K [ i ] &lt; = f K[i]&lt;=f K[i]<=f的情况 和无解的情况即可。

​ 如果最大的防御 f m a x &gt; A l l P [ i ]   fmax&gt;_{All}P[i]  fmax>All​P[i]  则无解。(其他形式的判断也行)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#define mset(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const ll maxn=1e5+100;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll H[maxn],F[maxn];
ll dp[11][1100];//初始化都为0
ll K[1100],P[1100];
int main()
{
    ll n,m;
    ll fmax=-1,hmax=-1;
    while(~scanf("%lld%lld",&n,&m))
    {
        fmax=hmax=-1;
        for(ll i=1; i<=n; ++i)
        {
            scanf("%lld%lld",H+i,F+i);
            fmax=fmax<F[i]?F[i]:fmax;
            hmax=hmax<H[i]?H[i]:hmax;
        }
        for(ll i=1; i<=m; ++i)
            scanf("%lld%lld",P+i,K+i);
        int flag=1;
        for(ll f=0; f<=fmax&&flag; ++f) //对于每个防御力 遍历生命值dp[f][0]=0
        {
            dp[f][0]=0;
            for(ll h=1; h<=hmax; ++h)
            {
                ll minn=inf;
                for(ll i=1; i<=m; ++i)
                {
                    if(K[i]<=f)
                        continue;
                    if(h+f<K[i])
                    {
                        minn=min(minn,P[i]);
                    }
                    else
                    {
                        minn=min(minn,dp[f][h-K[i]+f]+P[i]);
                    }
                }
                if(minn==inf)//不能够打死
                {
                    flag=0;
                    break;
                }
                dp[f][h]=minn;
            }
        }
        if(!flag)
        {
            printf("-1\n");
            continue;
        }
        ll ans=0;
        for(ll i=1; i<=n; ++i)
            ans+=dp[F[i]][H[i]];
        printf("%lld\n",ans);
    }
    return 0;
}