[机房测试] FSN

Description

远坂凛与卫宫士郎遭遇了 caster 召唤的龙牙兵的袭击，每个龙牙兵拥有生命值 \(L_i\) 与防御力 \(f_i\)。

远坂凛一共拥有 \(m\) 种类型的宝石攻击魔法，第 \(i\) 种魔法，需要消耗 \(k_i\) 个宝石，并对怪兽造成 \(g_i\) 点伤害。卫宫士郎只会物理攻击。

当然，如果远坂凛使用第 \(i\) 种魔法攻击第 \(j\) 个龙牙兵的话，会使得第 \(j\) 个龙牙兵的生命值减少 \(g_i-f_j\)，所以当攻击伤害小于防御力时，魔法就不会有效果。

而卫宫士郎的物理攻击可以无视龙牙兵的防御力，但每消灭一个龙牙兵，会损失 \(t_j\) 点体力值。

如果魔法攻击使龙牙兵 \(j\) 的生命值 \(L_j\leq 0\) 或者卫宫士郎花费 \(t_j\) 点体力值，那么龙牙兵 \(j\) 就会被消灭。

若卫宫士郎的体力值为 \(w\)，他一开始尽可能地消灭龙牙兵，然后远坂凛施法消灭剩下的龙牙兵。

若每种魔法都可以使用无限次，请问远坂凛最少携带多少宝石，就可以消灭剩下的龙牙兵。

\(f_i\leq 10\\ n,m,w,L_i,g_i,f_i,t_j\leq 10^3\\ k_i\leq 10^6 \)

Solution

数组开小了，喜得零分。

\(f\) 很小，可以考虑枚举，那么就可以预处理出 \(dp_{f,l}\) 表示防御为 \(f\)，血量为 \(l\) 的怪最少的花费。处理出之后，问题就转变成另一个 01 背包。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

typedef long long ll;

const int V=1e3;
const int N=3e3+7;

ll dp[11][N],Dp[N],a[N];
int L[N],f[N],t[N];
int k[N],g[N];

int main(){
//    freopen("fsn.in","r",stdin);
//    freopen("fsn.out","w",stdout);
    int n=read(),m=read(),w=read();
    for(int i=1;i<=n;i++)
        L[i]=read(),f[i]=read(),t[i]=read();
    for(int i=1;i<=m;i++)
        k[i]=read(),g[i]=read();
    memset(dp,63,sizeof(dp));
    for(int F=0;F<=10;F++)
    for(int i=1;i<=m;i++){
        if(F>=g[i]) continue;
        for(int j=0;j<=V;j++)
            dp[F][j]=min(dp[F][j],(j-g[i]+F<=0? 0:dp[F][j-g[i]+F])+k[i]);
    }
    ll s=0;
    for(int i=1;i<=n;i++) s+=(a[i]=dp[f[i]][L[i]]);
    for(int i=1;i<=n;i++)
        for(int j=w;j>=t[i];j--) Dp[j]=max(Dp[j],Dp[j-t[i]]+a[i]);
    printf("%lld",s-Dp[w]);
}

/*
1 2 3
4 5 4
10 7
9 6
*/