当前位置:网站首页>骑士战胜魔王(背包&dp)

骑士战胜魔王(背包&dp)

2022-07-07 01:25:00 Harris-H

骑士战胜魔王(背包&dp)

因为方案不同,取决于一个骑士使用的能量和不同。

因此我们考虑先用背包处理出每个骑士使用能量 i i i的最大伤害,求最大时为了包括所有情况。

然后进行dp,令 f ( i , j ) f(i,j) f(i,j)表示前 i i i个骑士造成 j j j 点伤害的方案数。

特别地, f ( i , m ) f(i,m) f(i,m) 表示前 i i i个骑士造成大于等于 j j j点伤害的方案数。

然后进行dp即可。

时间复杂度: O ( n × 3000 ) O(n\times 3000) O(n×3000)

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod = 998244353;

int n, m;

int fans[3009][3009], ff[3009];
int a[3009], b[3009];
void solved() {
    
    cin >> n >> m;
    fans[0][0] = 1;
    int s;
    for(int ttf = 1; ttf <= n; ttf ++) {
    
        cin >> s;
        for(int i = 0; i < s; i ++) cin >> a[i];
        for(int i = 0; i < s; i ++) cin >> b[i];
        for(int i = 0; i <= 3000; i ++) ff[i] = 0;  /// 初始化 dp 数组
        for(int i = 0; i < s; i ++) {
      /// 求出当前骑士花费的每种能量消耗可以造成的最大攻击力
            for(int j = 3000; j >= b[i]; j --) {
    
                if(ff[j - b[i]] || j - b[i] == 0)
                    ff[j] = max(ff[j - b[i]] + a[i], ff[j]);
            }
        }  /// n个骑士总时间复杂度: sum(s) * 3000
        for(int i = 0; i <= 3000; i ++) {
    
            if(ff[i] == 0 && i != 0) continue;  /// 有些值无法被表示,能被表示的值的量级为 sum(b)
            if(ff[i] > m) ff[i] = m;  /// 攻击力溢出处理
            for(int j = 0; j < ff[i]; j ++)  /// 这里是攻击力溢出部分的方案数,需要单独计算
                fans[ttf][m] = (fans[ttf][m] + fans[ttf - 1][m - j]) % mod;
            for(int j = m; j >= ff[i]; j --)  /// 这个 for 和上面一个 for 的总时间复杂度均为: sum(b) * m
                fans[ttf][j] = (fans[ttf][j] + fans[ttf - 1][j - ff[i]]) % mod;
        }  /// n个骑士这里的总时间复杂度: n * 3000
    }  /// 总时间复杂度: sum(s) * 3000 + n * 3000 + sum(b) * m
    cout << fans[n][m];
}
int main() {
    
    // int ttx; cin >> ttx; while(ttx --) 
        solved();
    return 0;
}
原网站

版权声明
本文为[Harris-H]所创,转载请带上原文链接,感谢
https://harris.blog.csdn.net/article/details/125645307