[luoguP1040] 加分二叉树(DP)
2024-08-23 10:38:17
区间DP水题
代码
#include <cstdio>
#include <iostream>
#define N 41
#define max(x, y) ((x) > (y) ? (x) : (y)) int n;
int a[N], f[N][N], pre[N][N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void solve(int l, int r)
{
printf("%d ", pre[l][r]);
if(l <= pre[l][r] - 1) solve(l, pre[l][r] - 1);
if(pre[l][r] + 1 <= r) solve(pre[l][r] + 1, r);
} int main()
{
int i, j, k;
n = read();
for(i = 1; i <= n; i++) f[i][i] = read(), pre[i][i] = i;
for(i = n; i >= 1; i--)
for(j = i + 1; j <= n; j++)
{
if(f[i][i] + f[i + 1][j] > f[i][j])
f[i][j] = f[i][i] + f[i + 1][j], pre[i][j] = i;
for(k = i + 1; k < j; k++)
if(f[i][k - 1] * f[k + 1][j] + f[k][k] > f[i][j])
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k], pre[i][j] = k;
if(f[j][j] + f[i][j - 1] > f[i][j])
f[i][j] = f[j][j] + f[i][j - 1], pre[i][j] = j;
}
printf("%d\n", f[1][n]);
solve(1, n);
return 0;
}
最新文章
- 让mysql不能为空的字段为空时也能插入
- amCharts图表中的JavaScript中文注释引起的浏览器兼容性问题
- teiid入门
- iOS之UI--指示器HUD的创建和设置
- Java学习-002-Java初识
- Majority Element
- AIM Tech Round 3 (Div. 2) A
- LINUX多线程(一)(创建和退出)
- 跟我一起学ruby (转)
- Search Insert Position--寻找插入点Given a sorted array and a target value, return the index if the target
- Bug Tracker
- Spring+SpringMVC+MyBatis+easyUI整合进阶篇(二)RESTful API实战笔记(接口设计及Java后端实现)
- Java---String总结
- Vue2leaflet 替换国内地图api,带{z}/{x}/{y}形式的
- python--网络编程urllib
- J2EE导论 | 疑惑篇
- Qt图片显示
- npm指向淘宝源
- spring boot 1.x完整学习指南(含各种常见问题servlet、web.xml、maven打包,spring mvc差别及解决方法)
- UVA1025 城市里的间谍
热门文章
- 水题 Codeforces Round #308 (Div. 2) A. Vanya and Table
- 题解报告:hdu 5750 Dertouzos(最大真约数、最小素因子)
- 题解报告:hdu1995汉诺塔V(递推dp)
- JSP页面自动刷新
- Safari兼容之new Date()格式问题
- sql 关键字的用法
- Android Studio 导入新工程项目
- Objective-C Memory Management 内存管理 2
- Win7 32位 遇到微软 silverlight 5.0安装失败的解决办法
- php从mysql数据库中取数据