首页 > 代码库 > 一种神奇的DP思想
一种神奇的DP思想
最近考了个叫做NOIP模拟的题。。。。。
真是难以吐槽。NOIP怎么考到了自动机去了。。。。。
当然，想我这种蒟蒻就只能膜拜机房里的各位大牛了。。。。
不管怎么说，我们来看一下这道很厉害的DP。
题目大意：
给定 N 个数， 请你将他们分成两组， 并使得两组的代价和最少
（每一组的代价定义为 ∑¦Hpi-1 - Hpi¦, pi-1 < pi）
我考场上只想到了 20 分的DP：令 f[i][j][k] 表示 考虑前 i 个 两组结尾分别为 j , k 时的最优值。
考试后，大牛就给了我一个 50 分算法：f[i][j] 表示 第一列以 i 结尾， 第二列以 j 结尾的最优值。（强制令 i > j）
那么很明显 f[i][j] -> f[i+1][i] 或 f[i+1][j]
:-( 怎么会这样呢？
第二天，大牛告诉我说他 AC 了， 一问才知道 他强制令 i - j <= 20 这样居然骗到了 95 分。。。(⊙o⊙)…
没办法，自己怎么会有那么厉害的YY能力？
只能看题解：
所以说不愧是题解
令 g[i] = f[i][i-1]
则 g[i] = min(g[j] + sum[i-1] - sum[j] + abs(H[i] - H[j-1])) （sum[i] = sum[i-1] + abs(Hi - Hi-1)）
那么我们对这个绝对值号进行分类讨论，那么就可以维护处最优解了。
我们用两棵树状数组来维护这个值 （即 g[j] - sum[j] ± H[j-1]）
我们先将 H[i] 离散化， 那么对于 H[i] > H[j] 查找的范围为 树状数组A [1 , i)
否则为 树状数组B (i, n]
代码就是这个样子的：
1 #include<cstdlib> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define maxn 500500 6 using namespace std; 7 long long n,h[maxn]; 8 long long sum[maxn]; 9 long long Bit1[maxn],Bit2[maxn];10 long long f[maxn];11 long long ans,a[maxn],tot;12 int lowbit(int x)13 {14 return x & (-x);15 }16 void change(long long bit[],int pos,long long x)17 {18 while(pos <= n){19 bit[pos] = min(bit[pos],x);20 pos += lowbit(pos);21 }22 }23 long long ask(long long bit[],int pos)24 {25 long long ret = 0x7fffffffff;26 while(pos){27 ret = min(ret,bit[pos]);28 pos -= lowbit(pos);29 }30 return ret;31 }32 int main()33 {34 freopen("sprung.in","r",stdin);35 freopen("sprung.out","w",stdout);36 scanf("%I64d",&n);37 memset(Bit1,0x3f,sizeof(Bit1));38 memset(Bit2,0x3f,sizeof(Bit2));39 f[0] = 0;40 ans = 0x7ffffffff;41 for(int i=1;i<=n;++i) scanf("%I64d",&h[i]),a[i] = h[i];42 sort(a+1,a+n+1); tot = unique(a+1,a+n+1) - a;43 for(int i=1;i<=n;++i) sum[i] = sum[i-1] + abs(h[i] - h[i-1]);44 change(Bit1,1,0);45 change(Bit2,tot,0);46 for(int i=2;i<=n;++i){47 int pos = lower_bound(a+1,a+tot,h[i]) - a + 1;48 long long x1 = ask(Bit1,pos) + h[i] ;49 long long x2 = ask(Bit2,tot - pos + 1) - h[i];50 f[i] = min(x1,x2) + sum[i-1];51 ans = min(ans,f[i] + sum[n] -sum[i]);52 pos = lower_bound(a+1,a+tot,h[i-1]) - a + 1;53 change(Bit1,pos,f[i] - sum[i] - h[i-1]);54 change(Bit2,tot - pos + 1,f[i] - sum[i] + h[i-1]);55 }56 printf("%I64d",ans);57 return 0; 58 }
一种神奇的DP思想