当前位置:网站首页>282. Stone consolidation (interval DP)
282. Stone consolidation (interval DP)
2022-07-06 00:53:00 【seez】
Application interval dp To think
State means : All merged i Pile up to the third j A collection of fruits
attribute :min
State calculation / subset division : Which two piles of fruits were merged last time , That is, where was the last breakpoint
- The break point is i+1 Merge [i] and [i+1,j] dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i,j]
- The break point is i+2 Merge [i,i+1] and [i+2,j] dp[i][j]=dp[i][i+1]+dp[i+2][j]+sum[i,j]
- ...
- The break point is j-1 Merge in [i,j-1] and [j] dp[i][j]=dp[i][j-1]+dp[j][j]+sum[i,j]
initialization : All are infinite
The border :dp[i][i]=0
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=305;
int a[N];
int s[N];
int dp[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],s[i]=s[i-1]+a[i];
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
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];
return 0;
}
边栏推荐
- Spark SQL空值Null,NaN判断和处理
- 数据分析思维分析方法和业务知识——分析方法(三)
- Gartner发布2022-2023年八大网络安全趋势预测,零信任是起点,法规覆盖更广
- Leetcode 44 Wildcard matching (2022.02.13)
- Novice entry depth learning | 3-6: optimizer optimizers
- Cannot resolve symbol error
- Lone brave man
- [groovy] compile time metaprogramming (compile time method interception | find the method to be intercepted in the myasttransformation visit method)
- 【线上小工具】开发过程中会用到的线上小工具合集
- Spark SQL null value, Nan judgment and processing
猜你喜欢
95后CV工程师晒出工资单,狠补了这个,真香...
Problems and solutions of converting date into specified string in date class
uniapp开发,打包成H5部署到服务器
Common API classes and exception systems
After 95, the CV engineer posted the payroll and made up this. It's really fragrant
Finding the nearest common ancestor of binary tree by recursion
The growth path of test / development programmers, the problem of thinking about the overall situation
Building core knowledge points
程序员搞开源,读什么书最合适?
cf:C. The Third Problem【关于排列这件事】
随机推荐
[groovy] compile time metaprogramming (compile time method interception | find the method to be intercepted in the myasttransformation visit method)
golang mqtt/stomp/nats/amqp
Extension and application of timestamp
【第30天】给定一个整数 n ,求它的因数之和
MIT博士论文 | 使用神经符号学习的鲁棒可靠智能系统
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
Building core knowledge points
Dynamic programming -- linear DP
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
Yolov5, pychar, Anaconda environment installation
Cannot resolve symbol error
Spark SQL空值Null,NaN判断和处理
cf:C. The Third Problem【关于排列这件事】
What is the most suitable book for programmers to engage in open source?
Finding the nearest common ancestor of binary tree by recursion
孤勇者
A preliminary study of geojson
CTF daily question day44 rot
Why can't mathematics give machine consciousness