当前位置:网站首页>骑士战胜魔王(背包&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;
}
边栏推荐
- 云加速,帮助您有效解决攻击问题!
- ML's shap: Based on the adult census income binary prediction data set (whether the predicted annual income exceeds 50K), use the shap decision diagram combined with the lightgbm model to realize the
- Swagger3 configuration
- MySQL performance_ Schema common performance diagnosis query
- 生活中的开销,怎么记账合适
- Markdown 并排显示图片
- A freshman's summary of an ordinary student [I don't know whether we are stupid or crazy, but I know to run forward all the way]
- yarn入门(一篇就够了)
- POI excel export, one of my template methods
- 话说SQLyog欺骗了我!
猜你喜欢
Go language learning notes - Gorm use - Gorm processing errors | web framework gin (10)
Rk3399 platform development series explanation (WiFi) 5.52. Introduction to WiFi framework composition
SAP Spartacus checkout 流程的扩展(extend)实现介绍
Deep clustering: joint optimization of depth representation learning and clustering
进程间通信之共享内存
go-microservice-simple(2) go-Probuffer
Rk3399 platform development series explanation (WiFi) 5.53, hostapd (WiFi AP mode) configuration file description
Apple CMS V10 template /mxone Pro adaptive film and television website template
每秒10W次分词搜索,产品经理又提了一个需求!!!(收藏)
cf:C. Column Swapping【排序 + 模拟】
随机推荐
SAP Spartacus checkout 流程的扩展(extend)实现介绍
You don't know the complete collection of recruitment slang of Internet companies
mac版php装xdebug环境(m1版)
Peripheral driver library development notes 43: GPIO simulation SPI driver
老板总问我进展,是不信任我吗?(你觉得呢)
[InstallShield] Introduction
[FPGA tutorial case 13] design and implementation of CIC filter based on vivado core
360织语发布7.0新品 为党政军、央国企打造专属“统一数字工作空间”
Ten stages of becoming a Senior IC Design Engineer. What stage are you in now?
Mac version PHP installed Xdebug environment (M1 version)
基于ADAU1452的DSP及DAC音频失真分析
你不知道的互联网公司招聘黑话大全
JVM命令之 jinfo:实时查看和修改JVM配置参数
JVM command - jmap: export memory image file & memory usage
Detailed explanation of platform device driver architecture in driver development
Rk3399 platform development series explanation (WiFi) 5.53, hostapd (WiFi AP mode) configuration file description
POI excel export, one of my template methods
SQL Server 2008 各种DateTime的取值范围
进程间通信之共享内存
【SQL实战】一条SQL统计全国各地疫情分布情况