51Nod 1022 石子归并 V2(区间DP+四边形优化)
2024-09-29 11:33:28
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1022
题目大意:
N堆石子摆成一个环。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如: 1 2 3 4,有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出,第一种方法的代价最低,现在给出n堆石子的数量,计算最小合并代价。
解题思路:经典的石子合并问题,较原来不同的是石子是环形摆放的,而且石子数目n的范围有100增加到了1000,原本O(n^3)的算法肯定是会超时的。所以需要用四边形不等式优化将复杂度降为O(n^2),并且将数组倍增把环变为链。
粗略介绍一下四边形优化的作用,具体证明看这里《动态规划加速原理之四边形不等式》。
我们原本的状态转移方程为dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]}(i<j,i<=k<=j)。
上式在动态规划的状态转移方程中是很常见的,对于上式中的w(i,j)
如果符合w(i`,j) <= w(i,j`) i<i`<j<j` 那么我们称函数w满足关于区间包含的单调性。
如果符合w(i,j)+w(i`,j`) <= w(i`,j)+w(i,j`) 那么我们称函数w满足四边形不等式。
如果符合w(i`,j) <= w(i,j`) i<i`<j<j` 那么我们称函数w满足关于区间包含的单调性。
如果符合w(i,j)+w(i`,j`) <= w(i`,j)+w(i,j`) 那么我们称函数w满足四边形不等式。
那么就可以使用两个定理(图片来源)
于是,我们可以使用s[i][j]记录使得dp[i][j]最优的分割点(k点),并且满足s[i][j-1]<=s[i][j]<=s[i+1][j+1],那么我们的k的枚举范围就是s[i][j-1]<=s[i][j]<=s[i+1][j+1]。
复杂度证明:
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e3+;
const int INF=0x3f3f3f3f; int dp[N][N],s[N][N],sum[N],a[N];//s[i][j]为使dp[i][j]最优的分割点 int main(){
int n;
scanf("%d",&n);
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=;i<=*n;i++){
dp[i][i]=;
sum[i]=sum[i-]+a[i];
s[i][i]=i;
}
for(int d=;d<n;d++){
for(int i=;i<=*n-d;i++){
int j=i+d;
for(int k=s[i][j-];k<=s[i+][j];k++){
int tmp=dp[i][k]+dp[k+][j]+sum[j]-sum[i-];
if(tmp<dp[i][j]){
dp[i][j]=tmp;
s[i][j]=k;
}
}
}
}
int ans=INF,d=n-;
for(int i=;i<=*n-d;i++){
int j=i+d;
ans=min(ans,dp[i][j]);
}
printf("%d\n",ans);
return ;
}
最新文章
- Clr编写Insert Triggr
- DOM事件类型详解
- Servlet工作原理(转)
- python学习小结6:模块
- UNIX标准化及实现之POSIX标准可选头文件
- # MongoDB学习笔记(持续更新)
- Java知识点复习
- 实现web多语言的一种解决办法
- git使用方法1
- 理解Java中的抽象
- JDBC的链接及封装
- angular&#160;如何获取使用filter过滤后的ng-repeat的数据长度
- C#检测获取移动硬盘盘符
- Spring Security入门(2-1)Spring Security - 重要的过滤器
- BZOJ_1801_[Ahoi2009]chess 中国象棋_DP
- .net core ef 通过dbfirst方式连接mysql数据库
- 通俗的理解java设计模式的准则
- socket 10060错误解决方案
- (去重 sort)nyoj8-一种排序
- Dubbo接口压测
热门文章
- The driver has not received any packets from the server
- 使用snmp4j实现Snmp功能(二)
- vijos 1002 简单压缩+DP
- Maven:Non-resolvable parent POM: Failure to find错误
- Python遍历文件夹和读写文件的方法
- Codeforces Round #484 (Div. 2)
- for in、each; for 、forEach、map
- 浅谈游戏中BUFF的设计要点
- javascript中null与undefined的区别
- JavaWeb使用Session防止表单重复提交