当前位置:网站首页>骑士战胜魔王(背包&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;
}
边栏推荐
- Senior programmers must know and master. This article explains in detail the principle of MySQL master-slave synchronization, and recommends collecting
- [cloud native] what is the microservice architecture?
- MySQL performance_ Schema common performance diagnosis query
- 深度聚类:将深度表示学习和聚类联合优化
- Jinfo of JVM command: view and modify JVM configuration parameters in real time
- 基于ADAU1452的DSP及DAC音频失真分析
- [云原生]微服务架构是什么?
- Chain storage of stack
- 693. 行程排序
- [daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree
猜你喜欢
Jstat of JVM command: View JVM statistics
Rk3399 platform development series explanation (WiFi) 5.52. Introduction to WiFi framework composition
PowerPivot - DAX (function)
你不知道的互联网公司招聘黑话大全
Go language learning notes - Gorm use - native SQL, named parameters, rows, tosql | web framework gin (IX)
JVM监控及诊断工具-命令行篇
Question 102: sequence traversal of binary tree
VScode进行代码补全
Why does the data center need a set of infrastructure visual management system
老板总问我进展,是不信任我吗?(你觉得呢)
随机推荐
深度聚类:将深度表示学习和聚类联合优化
Reading notes of Clickhouse principle analysis and Application Practice (6)
You don't know the complete collection of recruitment slang of Internet companies
Dc-7 target
How much do you know about clothing ERP?
SubGHz, LoRaWAN, NB-IoT, 物联网
Go language learning notes - Gorm use - Gorm processing errors | web framework gin (10)
Flask1.1.4 Werkzeug1.0.1 源碼分析:啟動流程
JVM命令之 jstat:查看JVM统计信息
软件测试的几个关键步骤,你需要知道
EMMC print cqhci: timeout for tag 10 prompt analysis and solution
软件测试知识储备:关于「登录安全」的基础知识,你了解多少?
JVM命令之- jmap:导出内存映像文件&内存使用情况
PowerPivot - DAX (function)
JVM监控及诊断工具-命令行篇
云加速,帮助您有效解决攻击问题!
老板总问我进展,是不信任我吗?(你觉得呢)
Storage of dental stem cells (to be continued)
【FPGA教程案例13】基于vivado核的CIC滤波器设计与实现
A very good JVM interview question article (74 questions and answers)