分级(线性DP)
DP 线性 分级
2023-09-11 14:20:29 时间
给定长度为 N 的序列 A,构造一个长度为 N的序列 B,满足:
B 非严格单调,即 B1≤B2≤…≤BN 或 B1≥B2≥…≥BN。
最小化 S=∑Ni=1|Ai−Bi|。
只需要求出这个最小值 S。
输入格式
第一行包含一个整数 N。
接下来 N 行,每行包含一个整数 Ai。
输出格式
输出一个整数,表示最小 S 值。
数据范围
1≤N≤2000
0≤Ai≤106
输入样例:
7
1
3
2
4
5
3
9
输出样例:
3
思考
解决这一题得明白一个性质:
最优解的b序列的每个元素都会出现在a序列中
所以从正面从反面各自求一遍取最小值
f[i][j] 代表所有给A[1] ~ A[i]分配好了值且最后一个B[i] = A'[j]的方案的集合
依据倒数第二个数分配的是哪个A'[i]将f[i][j]所代表的集合划分成j个不重不漏的子集
f[i][j]在所有子集的最小值中取min即可。
最终答案需要遍历最后一个数的所有取值,然后取min即可
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2010, INF = 0x3f3f3f3f;
int n;
int a[N], b[N], f[N][N];
int work(){
memcpy(b, a, sizeof b);
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++){
int minv = INF;
for(int j = 1; j <= n; j++){
minv = min(minv, f[i-1][j]);
f[i][j] = minv + abs(a[i] - b[j]);
}
}
int res = INF;
for(int i = 1; i <= n; i++) res = min(res, f[n][i]);
return res;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int res = work();
reverse(a + 1, a + 1 + n);
res = min(res, work());
cout<<res<<endl;
return 0;
}
相关文章
- 最长上升子序列(线性DP)
- 砝码称重(DP,背包问题)
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习3
- 【基础练习】【线性DP】codevs3027 线段覆盖2题解
- POJ 2479-Maximum sum(线性dp)
- hdu 4975 最大流问题解决队伍和矩阵,利用矩阵dp优化
- POJ 3280 间隔DP
- uva--562Dividing coins +dp
- hdu 4945 2048(DP)
- 有意思的DP(CF360B Levko and Array)
- 动态规划——dp[i]定义包含子状态,dp[i][2]这种,典型案例属于买卖股票,2表示 持有和不持有股票两种状态
- 377. Combination Sum IV——DP本质:针对结果的迭代,dp[ans] <= dp[ans-i] & dp[i] 找三者关系 思考问题的维度+1,除了数据集迭代还有考虑结果
- 1027. 方格取数(线性DP)
- 1018. 最低通行费(线性DP)