HDU 6082 度度熊与邪恶大魔王（DP）

D - 度度熊与邪恶大魔王

​ HDU - 6082

思路：

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

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

$dp\left[f\right]\left[h\right]=min\left(dp\right[f\left]\right[h+f-K\left[i\right]]+P[i\left]\right),i\in [1,m]\mathrm{\&}\mathrm{\&}K\left[i\right]\>f$dp[f][h]=min(dp[f][h+f−K[i]]+P[i]),i∈[1,m]&&K[i]>f​ 。 且 $dp\left[f\right]\left[0\right]=0$dp[f][0]=0​

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

​ 如果最大的防御 $fmax{\&gt;}_{All}P\left[i\right]$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;
}