LUOGU P1779 魔鬼杀手_NOI导刊2010提高（03）

解题思路

背包，首先先用aoe都打残然后单伤补刀，用f[i]表示AOE打了i的伤害的最小花费，g[i]表示单伤打了i的伤害的最小花费。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdio>

#include<cstring>

#define int long long

using namespace std;

const int MAXN = 105;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return f?x:-x;

}

int f[100005],g[100005],ans=0x3f3f3f3f;

int n,m,val[MAXN],cost[MAXN],hp[MAXN];

bool al[MAXN];

signed main(){

    n=rd();memset(f,0x3f,sizeof(f));

    memset(g,0x3f,sizeof(g));

    for(register int i=1;i<=n;i++) hp[i]=rd();

    m=rd();char c[MAXN],s[MAXN];

    for(register int i=1;i<=m;i++){

        scanf("%s",c+1);cost[i]=rd();

        scanf("%s",s+1);if(s[1]=='A') al[i]=1;

        val[i]=rd();

        if(cost[i]==0 && val[i]>0) {cout<<0<<endl;return 0;}

        if(val[i]>100000) val[i]=100000;

    }f[0]=0;g[0]=0;

    for(register int i=1;i<=m;i++){

        if(al[i]){

            for(register int j=val[i];j<=100000;j++)

                f[j]=min(f[j],f[j-val[i]]+cost[i]);

        }

        else {

            for(register int j=val[i];j<=100000;j++)

                g[j]=min(g[j],g[j-val[i]]+cost[i]);

        }

    }

    for(register int i=99999;i>=0;i--)

        if(g[i]>g[i+1]) g[i]=g[i+1];  //打了i+1的伤害就一定打了i的伤害

    for(register int i=0;i<=100000;i++) {

        int now=f[i];if(now>ans) continue;

        for(register int j=1;j<=n;j++){

            if(hp[j]>i) now+=g[hp[j]-i];

            if(now>ans) break;

        }

        ans=min(ans,now);

    }cout<<ans<<endl;

}

巴特西

LUOGU P1779 魔鬼杀手_NOI导刊2010提高（03）

解题思路

代码

最新文章

热门文章