当前位置:网站首页>Knight defeats demon king (Backpack & DP)
Knight defeats demon king (Backpack & DP)
2022-07-07 06:18:00 【Harris-H】
The knight defeated the demon king ( knapsack &dp)
Because the plan is different , It depends on the energy and difference used by a knight .
Therefore, we consider using backpacks to deal with the energy used by each Knight i i i The biggest damage , When seeking the maximum, in order to include all cases .
Then proceed dp, Make f ( i , j ) f(i,j) f(i,j) Before presentation i i i Knights caused j j j Number of schemes for point damage .
Specially , f ( i , m ) f(i,m) f(i,m) Before presentation i i i Knights cause greater than or equal to j j j Number of schemes for point damage .
Then proceed dp that will do .
Time complexity : 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; /// initialization dp Array
for(int i = 0; i < s; i ++) {
/// Find out the maximum attack power that each energy consumption of the current knight can cause
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 Total time complexity of knights : sum(s) * 3000
for(int i = 0; i <= 3000; i ++) {
if(ff[i] == 0 && i != 0) continue; /// Some values cannot be represented , The magnitude of the value that can be represented is sum(b)
if(ff[i] > m) ff[i] = m; /// Attack overflow processing
for(int j = 0; j < ff[i]; j ++) /// Here is the number of schemes in the attack overflow part , It needs to be calculated separately
fans[ttf][m] = (fans[ttf][m] + fans[ttf - 1][m - j]) % mod;
for(int j = m; j >= ff[i]; j --) /// This for And the one above for The total time complexity of is : sum(b) * m
fans[ttf][j] = (fans[ttf][j] + fans[ttf - 1][j - ff[i]]) % mod;
} /// n The total time complexity of a knight here : n * 3000
} /// Total time complexity : sum(s) * 3000 + n * 3000 + sum(b) * m
cout << fans[n][m];
}
int main() {
// int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
边栏推荐
- Redisl garbled code and expiration time configuration
- Go语学习笔记 - gorm使用 - gorm处理错误 | Web框架Gin(十)
- PowerPivot - DAX (function)
- Test the foundation of development, and teach you to prepare for a fully functional web platform environment
- Detailed explanation of platform device driver architecture in driver development
- 进程间通信之共享内存
- JVM monitoring and diagnostic tools - command line
- Bypass open_ basedir
- Deep clustering: joint optimization of depth representation learning and clustering
- 职场经历反馈给初入职场的程序员
猜你喜欢
Test the foundation of development, and teach you to prepare for a fully functional web platform environment
Jcmd of JVM command: multifunctional command line
JVM命令之 jstat:查看JVM統計信息
cf:C. Column Swapping【排序 + 模擬】
蚂蚁庄园安全头盔 7.8蚂蚁庄园答案
The solution of a simple algebraic problem
JMeter function assistant - random value, random string, fixed value random extraction
[FPGA tutorial case 14] design and implementation of FIR filter based on vivado core
如何在Touch Designer 2022版中设置解决Leap Motion不识别的问题?
Red hat install kernel header file
随机推荐
Oracle迁移中关于大容量表使用数据泵(expdp、impdp)导出导入容易出现的问题和注意事项
Red hat install kernel header file
[FPGA] EEPROM based on I2C
You don't know the complete collection of recruitment slang of Internet companies
JVM command - jmap: export memory image file & memory usage
VScode进行代码补全
postgresql 数据库 timescaledb 函数time_bucket_gapfill()报错解决及更换 license
Cf:c. column swapping [sort + simulate]
Change the original style of UI components
Laravel uses Tencent cloud cos5 full tutorial
Implementation of VGA protocol based on FPGA
Jstack of JVM command: print thread snapshots in JVM
On the discrimination of "fake death" state of STC single chip microcomputer
Jstat of JVM command: View JVM statistics
3531. 哈夫曼树
基本Dos命令
PowerPivot - DAX (function)
对称的二叉树【树的遍历】
Ctfshow-- common posture
蚂蚁庄园安全头盔 7.8蚂蚁庄园答案