hihocoder1636 Pangu and Stones
2024-09-07 19:45:17
思路:
区间dp。dp[l][r][k]表示把区间[l, r]的石子合并成k堆所需要的最小代价。
实现:
#include <iostream>
#include <cstring>
using namespace std; const int INF = 0x3f3f3f3f;
const int N = ; int a[N], sum[N], dp[N][N][N];
int n, L, R; int dfs(int l, int r, int k)
{
if (l == r) return k == ? : INF;
if (r - l + == k) return ;
if (dp[l][r][k] != -) return dp[l][r][k];
int ans = INF;
if (k == )
{
for (int i = L; i <= R; i++)
ans = min(ans, dfs(l, r, i) + sum[r] - sum[l - ]);
}
else
{
for (int i = ; i < r - l; i++)
ans = min(ans, dfs(l, l + i, ) + dfs(l + i + , r, k - ));
}
return dp[l][r][k] = ans;
} int main()
{
while (cin >> n >> L >> R)
{
memset(sum, , sizeof sum);
memset(dp, -, sizeof dp);
for (int i = ; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - ] + a[i];
}
int ans = dfs(, n, );
cout << (ans == INF ? : ans) << endl;
}
return ;
}
最新文章
- 洛谷P1755 斐波那契的拆分
- HDU 2082 母函数模板题
- CSS块级元素与行级元素(转载)
- ios 面试题 0
- linux配置本地tomcat应用80端口转发
- 五、oracle基本建表语句
- Qt之对话框消失动画
- Python自学笔记-进程,线程(Mr serven)
- Java build path &;&; Deployment assembly &;&; 编译路径 &;&; 发布路径
- Python Base64 编码
- (⊙o⊙)…
- Ubuntu安装后上网问题,
- 使用VSTS的Git进行版本控制(四)——在Visual Studio中管理分支
- 微信小程序避坑指南
- 树状数组区间加法&;区间求和操作
- 常见移动设备的 CSS3 Media Query 整理(iPhone/iPad/Galaxy/HTC One etc.)
- CISC, RISC 探究
- 域对象 request
- POJ 1321 棋盘问题(非常经典的dfs,入门题)
- [转]局域网共享一键修复 18.5.8 https://zhuanlan.zhihu.com/p/24178142
热门文章
- Ubuntu16.04 安装cuda9.0 cudnn 7.0.5
- kitti数据集标定文件解析
- This file requires _WIN32_WINNT to be #defined at least to 0x0403. Value 0x0501 or higher is recommended
- ETL 循环导入 平面文件
- conditon_variable(条件变量)用于线程间同步
- Java 类加载器的作用
- JAVA实现DIJKSTRA算法
- Python Matplotlib 中对于 bar 显示时间的问题
- 洛谷 P4704 太极剑【贪心】
- MySQL &#183; 性能优化 &#183; MySQL常见SQL错误用法