Aizu 2155 Magic Slayer 背包DP

这是上上次对抗赛的题目了

其实现在发现整个代码从头到尾，都是用了背包，怪我们背包没深入学好。

比赛的时候，聪哥提出的一种思路是，预处理一下，背包出 ALL攻击和 single攻击的血量对应的最小花费，其实这些都没什么问题。。。主要是后面的问题，后面为了找到如何使用ALL攻击是最好的，我们是这样处理的，对怪物血量升序排序，然后枚举，从哪个点开始，该点前面的怪物都用ALL杀死，后面的怪物都用single杀死，因为血高的放在后面多承受几次ALL攻击应该是最优的，这样看起来好像是对的。。也过了样例，就是WA了。。。。其实WA的很明显，我们居然三个人都没想到，刚刚重新敲这道题才发现这个策略大错特错了，我们这样枚举，很明显，没有计算，用了ALL攻击，但是没有杀死怪物的情况，也许这些就是最优解。。我们的策略，要么就不用ALL攻击，用了ALL攻击就一定要把怪物杀死。。。肯定有问题啊。

后来还是参考的别人的比较好的思路，前面的处理是一样的，不过换了一下，背包出两种攻击的花费对应的最大攻击，即下标是花费，值是攻击力，这样便于后面的处理。

背包完之后，从0开始往上枚举出使用ALL的花费情况，然后就得到ALL的攻击总量，再遍历一遍怪物，就可以得到剩余血量用single攻击的花费，全部加起来就是可能的结果，全部枚举完就能求出最优解

刚刚还和聪哥讨论了好久，为什么枚举ALL花费情况就可以得到所有合理的ALL攻击组合，这其实就是利用了背包的特性，即，我给你一个上限，就能帮我求出这个上限中的最优组合，就是利用了背包的特性。。。所以我为什么说这整个题目就是一个背包题，全部都在利用背包的特性。。怪我没有对背包理解透彻，这种隐藏的可以枚举花费，通过背包得到组合情况没有想到。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 110010

using namespace std;

int hp[];

struct weapon{

    int c,p;

}all[],sig[];

int dp[][N];

int all_num,sig_num;

int m,n;

void init()

{

    all_num=sig_num=;

}

void proc()

{

    memset(dp,,sizeof dp);

    for (int i=;i<all_num;i++){

       for (int j=all[i].c;j<N;j++){

         dp[][j]=max(dp[][j],dp[][j-all[i].c]+all[i].p);

       }

    }

    for (int i=;i<sig_num;i++){

        for (int j=sig[i].c;j<N;j++){

            dp[][j]=max(dp[][j],dp[][j-sig[i].c]+sig[i].p);

        }

    }

}

int bs(int val)

{

    int l=,r=N-,mid;

    while (l<r)

    {

        mid=(l+r)>>;

        if (dp[][mid]<val) l=mid+;

        else  r=mid;

    }

    return l;

}

int main()

{

    char ch[],cc[];

    int a,b;

    while (scanf("%d",&n)){

        if (!n) break;

        init();

        for (int i=;i<n;i++) scanf("%d",&hp[i]);

        scanf("%d",&m);

        bool flag=false;

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

            scanf("%s %d %s %d",ch,&a,cc,&b);

           // cout<<a<<" "<<b<<endl;

            if (cc[]=='A') all[all_num++]=(weapon){a,b};

            if (cc[]=='S') sig[sig_num++]=(weapon){a,b};

            if (a== && b>) flag=;

        }

        if (flag) {puts("");continue;}

        proc();

        int ans=N*;

        for (int i=;i<ans;i++){

            int temp=i;

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

                temp+=bs(hp[j]-dp[][i]);

            }

            ans=min(ans,temp);

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Aizu 2155 Magic Slayer 背包DP

最新文章

热门文章