POJ3666 线性dp_离散化_贪心

POJ3666 线性dp_离散化_贪心

就DP而言这个题不算难,但是难就难在贪心,还有离散化的思想上

题目大意:n个土堆,问你最少移动多少单位的图,可以使得这n个土堆变成单调的

dp[i][j]表示前i个土堆高变为j时最优值

dp[i][j] = abs(j - a[i]) + min(dp[i-1][k])

到这里就有问题了,k遍历起来有多大,是吧,没法想‘?

所以搜了题解才知道:贪心的思想:如果选了一个c[i]得到最优值,那么必然可以通过转换,使得最终序列花费不变,并全部用原序列的数。

也有一个大佬的证明

假设存在s <i <=i+1 <=⋯<=j <s+1  as<bi<=bi+1<=⋯<=bj<as+1    

情况一:如果这些b都相等,那么把这些b都改成s  as 或者s+1  as+1 肯定会有一种更优。

情况二:如果不全相等,那么肯定存在 p  p+1  p+2 ⋯q  bp bp+1 bp+2⋯bq ,他们的值相等,那么把他们移到左边的关键点或者右边的关键点,肯定有一种会更加优. 不断这样移动,最后就变成情况一了。

综上至少存在一种最优方案,最终的所有数都是原来的某个数。

因此可以离散化之后做dp,dp[i][j]表示把前i个数变成单调增(不严格)且第i个数变成原来第j大的数的最小代价。

这样关于k的遍历就好了但是我们真的还要去遍历k吗,只是一个最小值而已,只要记录一下不就好了

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#define inf (1 << 30)
using namespace std;
const int maxn = 2e3 + 2e2;
long long dp[maxn][maxn];
int a[maxn],b[maxn];
void init()
{
memset(dp,0,sizeof(dp));
}
//dp[i]表示前i个的最小花费
int main()
{
int n;
while(~scanf("%d",&n))
{
init();
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(b+1,b+1+n); for(int i = 1;i <= n;i++)
{
long long m = dp[i-1][1]; for(int j = 1;j <= n;j++)
{
m = min(m,dp[i-1][j]);//m记录的是第i-1个数小于等于j时最小值
dp[i][j] = abs(a[i] - b[j]) + m;//这里层次记录为了i+1个数做铺垫
} }
long long ans = inf;
for(int j = 1;j <= n;j++)
{
ans = min(ans,dp[n][j]);
}
printf("%lld\n",ans);
}
return 0;
}

POJ3666 线性dp_离散化_贪心

上一篇:Word隐藏回车符技巧


下一篇:AnyVal与AnyRef