HDU 6082도곰과 악의 대마왕(DP)

D - 도도곰과 사악한 대마왕

​ HDU - 6082

아이디어:

데이터가 매우 풍부해서 1000 ∗ 1000 ∗ 10 1000 * 10 1000 ∗ 1000 ∗ 10의 복잡도는 여러 그룹의 입력을 모두 통과할 수 있다.
dp[f][h]dp[f][h]dp[f][h]는 방어력이 ff인 혈액량이 hh가 소멸되는 데 필요한 최소 수정석 수량을 나타낸다.그러면 제 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​ . 또한 dp[f][0] = 0 dp[f][0]=0 dp[f][0]= 0
참고: K[i] < = f K[i] < = f K[i] < = f의 경우 및 해결 불가능한 경우
최대 방어력 fm a x > A l l P [i] fmax>{All}P[i] fmax>AllP[i]는 풀리지 않습니다.(다른 형식의 판단도 가능)

#include
#include
#include
#include
#include
#include
#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
");
            continue;
        }
        ll ans=0;
        for(ll i=1; i<=n; ++i)
            ans+=dp[F[i]][H[i]];
        printf("%lld
",ans);
    }
    return 0;
}