题解 P1779 【魔鬼杀手_NOI导刊2010提高（03）】

Sooke · 2017-11-03 19:22:14 · 题解

思路概述

极坑，细节极多，这是对本题的概括 = . =

读完题后，首先发现一个性质：用相同攻击方式杀敌，结果与顺序没有关系。

如何理解？通俗地说，如果现在有 3 个怪兽，我们使用法术 1 群体攻击一次，接着用法术 2 对怪兽 1 单体攻击一次，最后再用法术 1 群体攻击一次。假设 3 只怪兽都在这样的攻击下全部阵亡了，那么我们直接使用法术 1 群体攻击两次，最后才用法术 2 对怪兽 1 单体攻击，效果仍然是一样的。这样，我们就可以将杂乱的攻击方式整理成：先放群体攻击，再放单体攻击。

算法已经很显然了，群体攻击的伤害对任何怪兽都是有效的，如果仍有怪兽在群体攻击下没有死，我们再耗费法力用单体攻击补个刀。群体攻击的所有伤害，我们可以从 0（不群体攻击）到 100000（怪兽最大的血量）枚举，加上枚举量所需最小花费，再依次看每只怪兽有无血量剩余，有的话放一个该剩余血量的单体攻击，再加上单体攻击最小花费。

这是最后的过程而已。我们之前需要预处理一下。先给法术分类。我们设 f_i 为要作出刚好（不多不少） i 的群体伤害所需最小花费。这个过程我们可以用完全背包求解（因为同个法术可以施展多次。将类别为群体伤害的法术当做一个物品，请自行思考转移方程和依据是什么，应该不难看出）。类似地，设 v_i 为要作出至少（可以多不能少） i 的单体伤害所需最小花费，之所以是至少而不是刚好，是因为对于一只在群体伤害下仍然坚强活着的血量 3 的怪兽，不论使用 3 的单体攻击，还是 4 啊 100000 啊，他都得死。这个过程仍旧使用完全背包，不同之处是背包做完后还要逆序转移最小值一遍。

上面就是这道题的主要解法了。然而你以为这就能过了吗？本题坑点还多着~详见下面。

注意事项

坑点 1，统计和做背包的数组用 long long，并且初始化什么的要设的恰好，反正我是 (long long)1 << 50。
坑点 2，注意有耗费为 0 的法术，此时如果它伤害大于 0，就用它了呗！直接输出 0 退出程序。
坑点 3，有伤害等于 0 的法术，此时需要过滤。
坑点 4，有伤害大于 100000 的法术，出于怪兽的血量最多也就 100000，将那个法术的伤害削成 100000，效果相同。
值得注意的就上面这些坑点了，如果还有第 5 个坑点，应该是您代码的问题了吧……

代码实现

（注：已经小小修改了一个地方，不要直接复制交上去了）

#include <iostream>
#include <cstring>

using namespace std;

int n , m , a[101] , b[101] , c[101];
long long res , ans = (long long)1 << 50 , f[100001] , v[100001];
bool u[101];
string s;

int main(){
    cin >> n; // 输入怪兽数量 
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i]; // 输入每个怪兽的血量 
    cin >> m; // 输入法术数量
    for(int i = 1 ; i <= m ; i++){
        cin >> s; // 输入（没有用的）法术名字
        cin >> b[i]; // 输入法术花费
        cin >> s; // 输入法术类型
        u[i] = (bool)(s == "A11"); // 将法术类型转换成逻辑值
        cin >> c[i]; // 输入法术伤害
        if(c[i] == 0){
            i-- , m--; // 法术没有伤害，可以废掉 
            continue;
        }
        if(c[i] > 100000)
            c[i] = 100000; // 法术伤害过高，削掉一点 
        if(b[i] == 0){
            cout << 0 << endl; // 花费为 0 伤害不为 0，很坑，直接免费用完 
            return 0;
        }
    } // 上面的输入完全可以缩成一行啊 QAQ
    // f[i] 表示群体伤害时刚好伤害 i 血最小花费
    // v[i] 表示单体伤害时至少伤害 i 血最小花费（两个不一样！） 
    for(int i = 1 ; i <= 100000 ; i++)
       f[i] = v[i] = (long long)1 << 50; // 初始化 
    for(int i = 1 ; i <= m ; i++)
        if(u[i]) // 确定为群体伤害 
            for(int j = c[i] ; j <= 100000 ; j++)
                if(f[j] > f[j - c[i]] + b[i])
                    f[j] = f[j - c[i]] + b[i]; // 跑一遍完全背包（法术可以放多次） 
    for(int i = 1 ; i <= m ; i++)
        if(!u[i]) // 确定为单体伤害 
            for(int j = c[i] ; j <= 100000 ; j++)
                if(v[j] > v[j - c[i]] + b[i])
                    v[j] = v[j - c[i]] + b[i]; // 再跑一遍完全背包，注意数组不同 
    for(int j = 99999 ; j >= 0 ; j--)
        if(v[j] > v[j + 1])
            v[j] = v[j + 1]; // 造成 j+1 点伤害，其实也造成了至少 j 点伤害，可以转移 
    // 最后，我们枚举群体伤害有多少，剩下打不死就用个体伤害咯 
    for(int i = 0 ; i <= 100000 ; i++){
        res = f[i]; // 群体伤害所需最小花费
        for(int j = 1 ; j <= n ; j++)
            if(a[j] - i > 0)
                res += v[a[j] - i]; // 打不死，用个体伤害，还要多的花费
        if(ans > res)
            ans = res; // 更新最小总花费 
    }
    cout << ans << endl; // 输出最小总花费 
    return 0;
}