题意：给你一个序列A 构造一个序列B 使得B单调上升或单调下降 求序列B-序列A的绝对值的和的最小值
思考可知 序列B一定是由序列A中的数得来的
所以用dp[i][j]记录把第i个数换成B[j]的最小花费
dp[i][j] = min(dp[i-1][1~j]+abs(A[i]-B[j]));
实际操作中第一层dp[i]没有什么意义 所以可以直接省略 很迷的一道题 真滴迷
【算法竞赛进阶指南|POJ 3666 玄学dp】AC代码：
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
int dp[2010];
int A[2010];
int B[2010];
int main()
{
int n;
cin >> n;
for(int i = 1;
i <= n;
i++)
{
cin >> A[i];
B[i] = A[i];
}
sort(B+1,B+1+n);
for(int i = 1;
i <= n;
i++)
{
int z = inf;
for(int j = 1;
j <= n;
j++)
{
z = min(dp[j],z);
dp[j] = z + abs(B[j] - A[i]);
}
}
int ans = inf;
for(int i = 1;
i <= n;
i++)
{
ans = min(ans,dp[i]);
}
cout< 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）