\(\color{#0066ff}{ 题目描述 }\)
在一个圆形操场的四周摆放 N 堆石子, 现要将石子有次序地合并成一堆. 规定每次只能选相邻的 2 堆合并成新的一堆, 并将新的一堆的石子数, 记为该次合并的得分.
试设计出 1 个算法, 计算出将 N 堆石子合并成 1 堆的最小得分和最大得分.
\(\color{#0066ff}{输入格式}\)
数据的第 1 行试正整数 N,1≤N≤100, 表示有 N 堆石子. 第 2 行有 N 个数, 分别表示每堆石子的个数.
\(\color{#0066ff}{输出格式}\)
输出共 2 行, 第 1 行为最小得分, 第 2 行为最大得分.
- \(\color{
- #0066ff
- }{
输入样例
- }\)
- 4 4 5 9 4
- \(\color{
- #0066ff
- }{
输出样例
- }\)
- 43 54
- \(\color{
- #0066ff
- }{
数据范围与提示
- }\)
- none
- \(\color{
- #0066ff
- }{
题解
}\)
对于这数据, 就是一 sb 的区间 DP
如果要 \(O(N^2)\) 做的话, 就要进行四边形不等式优化
那么什么时候才能用这种玄学的东西呢
1, 区间包含单调性
这是什么??
我们假设有一个区间序列 \([l_1,r_1],[l_2,r_2]\dots[l_n,r_n]\)
对于任意相邻两个区间, 满足后者包含前者, 并且每个区间的代价呈单调递增或递减, 就是区间包含单调性
2, 观察 (雾
先写出暴力的 DP, 然后把决策点打表, 看是否单调即可
本题最小值是可以优化的, 最大值不满足性质, 但是可以贪心
不难发现, 每次决策点取两边, ans 最大
- #include<bits/stdc++.h>
- #define LL long long
- LL in() {
- char ch; LL x = 0, f = 1;
- while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
- for(x = ch ^ 48; isdigit(ch = getchar()); x = (x <<1) + (x <<3) + (ch ^ 48));
- return x * f;
- }
- const int maxn = 350;
- const int inf = 0x3f3f3f3f;
- int n;
- int f[maxn][maxn], g[maxn][maxn], s[maxn], a[maxn], min = inf, max, pos[maxn][maxn];
- int main() {
- n = in();
- for(int i = 1; i <= n; i++) a[i + n] = a[i] = in();
- for(int i = 1; i <= (n <<1); i++) s[i] = s[i - 1] + a[i], pos[i][i] = i;
- for(int L = 2; L <= n; L++) {
- for(int l = 1, r = l + L - 1; r <= (n <<1); l++, r++) {
- g[l][r] = inf;
- for(int k = pos[l][r - 1]; k <= pos[l + 1][r]; k++) {
- int now = g[l][k] + g[k + 1][r] + s[r] - s[l - 1];
- if(g[l][r]> now) g[l][r] = now, pos[l][r] = k;
- }
- f[l][r] = std::max(f[l][r], std::max(f[l][l] + f[l + 1][r], f[l][r - 1] + f[r][r]) + s[r] - s[l - 1]);
- if(L == n) max = std::max(max, f[l][r]), min = std::min(min, g[l][r]);
- }
- }
- printf("%d\n%d", min, max);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2964384.html