删数
链接：https://www.luogu.com.cn/problem/P2426
题目描述
有 \(N\) 个不同的正整数 \(x_1\), \(x_2\), ..., \(x_N\) 排成一排，我们可以从左边或右边去掉连续的 \(i\) \((1 \le i \le n)\) 个数（只能从两边删除数），剩下 \(N-i\) 个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。
每次操作都有一个操作价值，比如现在要删除从 \(i\) 位置到 \(k\) 位置上的所有的数。操作价值为 \(|x_i-x_k| \times (k-i+1)\) ，如果只去掉一个数，操作价值为这个数的值。
问如何操作可以得到最大值，求操作的最大价值。
输入格式
第一行为一个正整数 \(N\) ;
第二行有 \(N\) 个用空格隔开的 \(N\) 个不同的正整数。
输出格式
一行，包含一个正整数，为操作的最大值
样例 #1
样例输入 #1
6
54 29 196 21 133 118
样例输出 #1
768
提示
【样例解释和说明】
说明，经过 \(3\) 次操作可以得到最大值，第一次去掉前面 \(3\) 个数：\(54\) 、\(29\) 、\(196\) ，操作价值为 \(426\)。第二次操作是在剩下的三个数 \((21,133,118)\) 中去掉最后一个数\(118\)，操作价值为 \(118\)。第三次操作去掉剩下的 \(2\) 个数：\(21\) 和 \(133\) ，操作价值为 \(224\)。操作总价值为 \(426+118+224=768\) 。
【数据范围】
\(3≤N≤100\) ，\(1 \le x_i \le 1000\)
解答
取巧做法
- 因为一次可以删除前面任意个数和后面任意个数，转换为区间 dp
- 最终都会是只删除前和后，区间两端，和区间 dp 异曲同工之妙
- 唯一难受的是既要删除后面，又要删除前面情况，不好讨论
- 转换为只用删前面，会存在最优解，因为删后面和前面算法一样，值一样，删除的区间 + 前面删除的区间 == 考虑全从前面删，区间 dp 思想考虑这个问题
- 所以
f[i]定义为删除到i的最优解
#include <iostream>
using namespace std;
const int N = 1010;
int a[N];
int f[N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
f[i] = a[i] + f[i - 1];
for (int j = 1; j < i; j++)
f[i] = max(f[i], f[j - 1] + (i - j + 1) * abs(a[i] - a[j]));
}
cout << f[n];
return 0;
}
中规中矩做法
- 区间 dp
f[i][j]：表示删除i~j之间数的方案数，价值最优值- 第三层循环即是
i~j之间枚举中间点 - 两次三层循环是因为考虑删除前面和后面数两种情况
#include <iostream>
using namespace std;
const int N = 110;
int a[N];
int f[N][N];
int n;
int t(int i, int j)
{
if (i == j) return a[i];
else return abs(a[i] - a[j]) * abs(j - i + 1);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
{
for (int k = i; k <= j; k++)
f[i][j] = max(f[k + 1][j] + t(i, k), f[i][j]);
for (int k = i; k <= j; k++)
f[i][j] = max(f[i][k] + t(k + 1, j), f[i][j]);
}
printf("%d", f[1][n]);
return 0;
}