luogu1063 能量项链
2024-08-31 05:57:02
题目大意
有一串项链,项链上的每个珠子有首尾两个数字,首尾相连的两个珠子的尾数字和头数字相同。每次选择相连的一对珠子,得到第一个项链的首数字*第一个项链的尾数字(第二个项链的首数字)*第二个项链的尾数字的能量,并将两个珠子合并,首数字为原来第一个项链的首数字,尾数字为第二个项链的尾数字,直到只剩一个珠子为止。问每次得到的能量之和的最大值。
错误思路
本题可以换一个说法:输入数据中的数字组成一个环,每次选连续三个数字,结果加上三个数字乘积,再将中间数字去除。
我们发现这道题跟“合并果子”有些像。于是我们有一个贪心思路:每次选择环中最小的数字,将该数字和左右两侧的两个数字作为当前选择的三个数字,然后将该数字从环中删除。这样做的理由是这会使数值更大的数字被乘的次数更多,贡献更大。但是这种做法错在不能保证很大的数字乘足够多次。
那么我们可以想想动规,但这种选三去一的选择方式使我们无法写出递归式。
正解
以项链为单位进行区间DP(拆开二倍)即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX_N = 210;
int HeadVal[MAX_N], F[MAX_N][MAX_N]; int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &HeadVal[i]);
HeadVal[i + n] = HeadVal[i];
}
HeadVal[n * 2 + 1] = HeadVal[1];
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n * 2 - len + 1; i++)
for (int lLen = 1; lLen <= len - 1; lLen++)
F[i][i + len - 1] = max(F[i][i + len - 1], F[i][i + lLen - 1] + F[i + lLen][i + len - 1] + HeadVal[i] * HeadVal[i + lLen] * HeadVal[i + len]);
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, F[i][i + n - 1]);
printf("%d\n", ans);
return 0;
}
最新文章
- Struts的文件上传下载
- CFURLCreateStringByAddingPercentEscapes与CFURLCreateStringByReplacingPercentEscapesUsingEncoding
- Tapestry
- 【BZOJ 4516】【SDOI 2016】生成魔咒
- IOS-CoreAnimation
- aehyok.com的成长之路一——开篇
- curl命令常见用法汇总 good
- 内容模块PC标签调用说明
- Java实战之03Spring-03Spring的核心之AOP(Aspect Oriented Programming 面向切面编程)
- JSON 与List转换类封装
- nosql数据库选型
- HDU 1199 - Color the Ball 离散化
- 《NoSQL精粹》读书笔记
- NPOI操作Excel 踩坑记
- [sklearn]官方例程-Imputing missing values before building an estimator 随机填充缺失值
- 值得注意的CSS属性
- SpringCloud微服务负载均衡与网关
- Javascript高级编程学习笔记(76)—— 表单(4)选择文本
- inux下配置rsyncd服务
- 完全背包-hdu1114