CCF(压缩编码):动态规划+平行四边形优化
2024-10-19 08:33:01
压缩编码
201612-4
- 一开始看这题还以为是哈夫曼编码的题目,结果是哈夫曼题目的变形。
- 哈夫曼编码是每次合并任意两堆石子,而这里的题目是合并相邻的两堆石子,而且这里的合并花费是合并两堆石子加上所有的叶子结点。
- 参考图解:https://blog.csdn.net/more_ugly_less_bug/article/details/60142954
- 石子问题:https://blog.csdn.net/acdreamers/article/details/18039073
#include<bits/stdc++.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
const int maxn=1003;
int n;
int sum[maxn];
int dp[maxn][maxn];
const int INF=0X3F3F3F3F;
//dp[i][j]=min(dp[i][k]+dp[k][j]+sum[j]-sum[i-1])
int main() {
//freopen("in1.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int x;
sum[0]=0;
for(int i=1;i<=n;i++){
cin>>x;
sum[i]=sum[i-1]+x;
}
memset(dp,INF,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][i]=0;
}
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++){
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]));
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
最新文章
- ex2-注释和井号
- ORA-00907: 缺失右括号
- mysql-5.7.13-win32 安装
- Swift3.0基础语法学习<;五>;
- SSH框架整合配置所需JAR包(SSH整合)
- Sklearn库例子2:分类——线性回归分类(Line Regression )例子
- 以程序的方式操纵NTFS的文件权限
- ORACLE 实验一
- 全面了解Android热修复技术
- How to Quickly Create a Copy of a Table using Transact-SQL
- 裸板驱动总结(makefile+lds链接脚本+裸板调试)
- Use LiveCD to acquire images from a VM
- 设置和取消git代理
- 相机标定问题-Matlab &; Py-Opencv
- adb环境配置+常用adb命令+Logcat命令的用法+手动进行文件比对的方法+批量挪bug
- ssm框架的整合搭建(二)
- 前端传递给后端且通过cookie方式,尽量传递id
- oracle 常用 sql
- spring boot ---->; spring boot 和spring的联系
- iOS-引用计数与ARC(转)