当前位置:网站首页>Explanation report of the explosion
Explanation report of the explosion
2022-07-05 15:25:00 【wch(】
The explosion's runes and cards are full of explanation reports
label : Dynamic programming
source : Cattle from
Their thinking :
The obvious knapsack problem
But observe again a,b Data range of , I can't drive that big dp Array
This inspires us to optimize , Because the title requires magic, the total cost is k Multiple
We can spend magic power on every data k modulus
Use dp[][j] Save directly in After taking the mold, the sum of magic is j The greatest power of time
Then the dynamic transfer equation :
dp[i][j] = max(dp[i-1][j],dp[i-1][((j-a)%k+k)%k]+b);
After doing this, I found that it is the same as the problem of nine people and nine doors in nine hours , It's a pity that I didn't do it during the game
Code implementation :
#include <bits/stdc++.h>
using namespace std;
long long dp[1050][1050];
int main(){
int n,k;
cin>>n>>k;
int a,b;
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
cin>>a>>b;
for(int j=0;j<k;j++){
dp[i][j] = max(dp[i-1][j],dp[i-1][((j-a)%k+k)%k]+b);
}
}
long long ans = dp[n][0];
if(ans<=0) ans=-1;
cout<<ans<<endl;
return 0;
}
边栏推荐
- 如何将 DevSecOps 引入企业?
- Au - delà du PARM! La maîtrise de l'Université de Pékin propose diverse pour actualiser complètement le classement du raisonnement du NLP
- 1330: [example 8.3] minimum steps
- 超越PaLM!北大硕士提出DiVeRSe,全面刷新NLP推理排行榜
- JS topic - console log()
- 机器学习框架简述
- Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
- Surpass palm! Peking University Master proposed diverse to comprehensively refresh the NLP reasoning ranking
- ionic cordova项目修改插件
- CPU design practice - Chapter 4 practice task 3 use pre delivery technology to solve conflicts caused by related issues
猜你喜欢
I include of spring and Autumn
Select sort and bubble sort
Photoshop plug-in action related concepts actionlist actiondescriptor actionlist action execution load call delete PS plug-in development
Good article inventory
可视化任务编排&拖拉拽 | Scaleph 基于 Apache SeaTunnel的数据集成
市值蒸发超百亿美元,“全球IoT云平台第一股”赴港求生
How can I quickly check whether there is an error after FreeSurfer runs Recon all—— Core command tail redirection
OSI 七层模型
Bugku's Eval
Machine learning notes - gray wolf optimization
随机推荐
百亿按摩仪蓝海,难出巨头
Au - delà du PARM! La maîtrise de l'Université de Pékin propose diverse pour actualiser complètement le classement du raisonnement du NLP
Coding devsecops helps financial enterprises run out of digital acceleration
Ctfshow web entry explosion
What are CSRF, XSS, SQL injection, DDoS attack and timing attack respectively and how to prevent them (PHP interview theory question)
PHP high concurrency and large traffic solution (PHP interview theory question)
P1451 求细胞数量/1329:【例8.2】细胞
CODING DevSecOps 助力金融企业跑出数字加速度
GPS original coordinates to Baidu map coordinates (pure C code)
Leetcode: Shortest Word Distance II
Common PHP interview questions (1) (written PHP interview questions)
Ctfshow web entry information collection
华为哈勃化身硬科技IPO收割机
Bugku alert
计算中间件 Apache Linkis参数解读
JS topic - console log()
Super wow fast row, you are worth learning!
可转债打新在哪里操作开户是更安全可靠的呢
Common interview questions about swoole
Visual task scheduling & drag and drop | scalph data integration based on Apache seatunnel