当前位置:网站首页>Interval DP (gravel consolidation)
Interval DP (gravel consolidation)
2022-07-05 15:35:00 【Xuanhong Zhou】
I finally posted an article , The computer was repaired yesterday
Paste the code directly , Because I'm going to play football
/* Section DP Interval dynamic programming is an extension of linear dynamic programming , It's dividing problems in stages , It has a lot to do with the order in which elements appear in the phase and which elements are merged from the previous phase The key word is merging , That is, the interval of a problem can be divided into two parts and merged , Then each part of the can be further decomposed Thinking of this topic : Note that only two adjacent heaps can be merged The interval [i,j] The stones in the merge , The last merger is bound to merge the left and right piles . Therefore, we can know the consolidation interval [i,j] The minimum value of is to merge the minimum value of the left pile plus the minimum value of the right pile, and then add the value of this merge But how to decide where to divide the left and right piles , Then you can only traverse . Divide into two piles, and then continue to divide according to the above ideas . Similar to the idea of partition When writing code , First write short intervals and then gradually merge them into large intervals min(i,j)=min(i,k)+min(k+1,j)+s[j]-s[i-1]; Section dp Common templates : Traversal interval length Traverse the left endpoint Traversal classification */
#include<iostream>
using namespace std;
const int M=310;
int N;
int stones[M];
int dp[M][M];
int s[M];// Prefixes and arrays
int main(){
cin>>N;
for(int i=1;i<=N;i++){
cin>>stones[i];
s[i]=s[i-1]+stones[i];
}
for(int len=2;len<=N;len++){
for(int i=1;i+len-1<=N;i++){
int j=i+len-1;
dp[i][j]=1e8;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
}
}
}
cout<<dp[1][N]<<endl;
return 0;
}
边栏推荐
- Ionic Cordova project modification plug-in
- Common redis data types and application scenarios
- 复现Thinkphp 2.x 任意代码执行漏洞
- Database learning - Database Security
- lv_font_conv离线转换
- I include of spring and Autumn
- 【簡記】解决IDE golang 代碼飄紅報錯
- 1330: [example 8.3] minimum steps
- Misc Basic test method and knowledge points of CTF
- Bugku's Eval
猜你喜欢
First PR notes
[brief notes] solve the problem of IDE golang code red and error reporting
12 MySQL interview questions that you must chew through to enter Alibaba
Example of lvgl display picture
Redis' transaction mechanism
Codasip为RISC-V处理器系列增加Veridify安全启动功能
做研究无人咨询、与学生不交心,UNC助理教授两年教职挣扎史
swiper. JS to achieve barrage effect
Transfer the idea of "Zhongtai" to the code
F. Min cost string problem solving Report
随机推荐
可转债打新在哪里操作开户是更安全可靠的呢
Brief introduction of machine learning framework
episodic和batch的定义
一文搞定vscode编写go程序
Array sorting num ranking merge in ascending order
MySQL5.7的JSON基本操作
ionic cordova项目修改插件
go语言编程规范梳理总结
力扣今日题-729. 我的日程安排表 I
Appium自动化测试基础 — APPium基础操作API(一)
六种常用事务解决方案,你方唱罢,我登场(没有最好只有更好)
Reasons and solutions for redis cache penetration and cache avalanche
Summary of the third class
Garbage collection mechanism of PHP (theoretical questions of PHP interview)
超越PaLM!北大硕士提出DiVeRSe,全面刷新NLP推理排行榜
Bugku's Ping
The difference between abstract classes and interfaces in PHP (PHP interview theory question)
R 熵权法计算权重及综合得分
B站做短视频,学抖音死,学YouTube生?
[JVM] operation instruction