Luogu【P1880】石子合并(环形DP)
2024-09-05 06:51:19
先放上luogu的石子合并题目链接
这是一道环形DP题,思想和能量项链很像,在预处理过程中的手法跟乘积最大相像。
用一个m[][]数组来存储石子数量,m[i][j]表示从第 i 堆石子到第 j 堆石子的总数。
接下来三重循环
i 表示合并操作的起始位置, j 表示合并操作的终点,也就是把 i 到 j 合并
k表示间断点,即 i 到 j 合并过程中选择k点来作为合并位置
状态转移方程
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+m[i][k]+m[k+1][j]);
d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+m[i][k]+m[k+1][j]);
注意该题有一个拆环为链的思想,设从1到n的石子数为12345
实际存到数组里的就是123451234
这样化成链就可以避免复杂的取余 毕竟作者循环队列学的不好,用一个环做的话一会就搞晕了
最后贴代码
#include<iostream>
#include<cstring>
using namespace std;
int q[];
int m[][];
int f[][];
int d[][];
int main(){
//memset(d,127/3,sizeof(d));
int n;
cin>>n;
for(int i=;i<=n;++i){
cin>>q[i];
q[i+n]=q[i];
}
m[][]=q[];
for(int i=;i<=n*-;++i) m[][i]=m[][i-]+q[i];
for(int i=;i<=n*-;++i)
for(int j=i;j<=n*-;++j)
m[i][j]=m[][j]-m[][i-];
for(int i=n*-;i>=;--i)
for(int j=i+;j<=i+n&&j<n*;++j){
d[i][j]=0x7fffffff;
for(int k=i;k<j;++k){
f[i][j]=max(f[i][j],f[i][k]+f[k+][j]+m[i][k]+m[k+][j]);
d[i][j]=min(d[i][j],d[i][k]+d[k+][j]+m[i][k]+m[k+][j]);
}
}
int maxx=,minn=0x7fffffff;
for(int i=;i<=n;++i){
minn=min(minn,d[i][i+n-]);
maxx=max(maxx,f[i][i+n-]);
}
cout<<minn<<endl<<maxx;
return ;
}
最新文章
- linux yum命令详解-转
- struts2校验总结
- ssh免密登录
- MONO Jexus部署最佳体验
- PMO究竟啥样?(3)
- PHP下通过file_get_contents\curl的方法实现获取远程网页内容(别忘了还有PhpRPC)
- 从0到1一步步搭建代码质量检测系统~iOS
- 1.5编程基础之循环控制44:第n小的质数
- IBM Websphere 集群会话共享问题解决办法
- Who do you want to be bad? (谁会是坏人?)人工智能机器小爱的问话
- C# 读写本地配置文件
- pandas(二)
- Flutter 知识点
- IntelliJ IDEA 常用设置
- Aspose.word
- Oracle下PLSQL连接没有数据库的问题
- Git 命令操作记录
- 8种常被忽视的SQL错误用法
- phpcms URL
- Kafka具体解释五、Kafka Consumer的底层API- SimpleConsumer