Making the Grade(POJ3666)
题目大意：
给出长度为n的整数数列,每次可以将一个数加1或者减1,最少要多少次可以将其变成单调增或者单调减(不严格).
题解：
1.一开始我有一个猜想,就是不管怎么改变,最终的所有数都是原来的某个数。然而我并不会证明,然而我属于那种不彻底弄清楚就不会去写的那种顽固分子,于是就拖了好几天。网络上有很多关于此题的题解,确实用了这个猜想来离散化,但是都是讲怎么dp,然后最后扯一句“由于数据比较大,可以离散化”之类的话,要么就是相当粗略的证明(也许已经说的够清楚了只不过我没理解...)。
2.今天早上起来洗漱的时候,感觉头脑比较清醒,再次想了一下这个问题,想到一个自认为正确的证明：
记原来的数从小到大排序后分别是$a_1 a_2 a_3cdots a_n$ 修改后从左到右分别是$b_1 b_2 b_3cdots b_n$. 为了方便描述,在数轴上标出这些点,称为关键点。
假设存在$a_s<b_i<=b_{i+1}<=cdots <=b_j<a_{s+1}$
情况一：如果这些b都相等,那么把这些b都改成$a_s$或者$a_{s+1}$ 肯定会有一种更优。
情况二：如果不全相等,那么肯定存在 $b_p b_{p+1} b_{p+2}cdots b_q$,他们的值相等,那么把他们移到左边的关键点或者右边的关键点,肯定有一种会更加优. 不断这样移动,最后就变成情况一了。
综上至少存在一种最优方案,最终的所有数都是原来的某个数。
因此可以离散化之后做dp,dp[i][j]表示把前i个数变成单调增(不严格)且第i个数变成原来第j大的数的最小代价。
dp[i][j]=min{dp[i-1][1...j]}+abs(a[i]-b[j]).
单调减(不严格)的情况也一样,更加方便的是可以把原数组倒转后做单调增的dp。
另外这题和CF Codeforces Round #371 (Div. 1)的C题类似,有个超简单的nlogn做法。可以看这篇：http://www.cnblogs.com/vb4896/p/5894578.html
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <set> 10 using namespace std; 11 12 #define X first 13 #define Y second 14 #define Mod 1000000007 15 #define N 3010 16 typedef long long ll; 17 typedef pair<int,int> pii; 18 19 inline int Mul(int x,int y){return 1ll*x*y%Mod;} 20 inline int Add(int x,int y){return ((x+y)%Mod+Mod)%Mod;} 21 22 int n,m; 23 int a[N],b[N]; 24 ll dp[N][N],Ans=1ll<<60; 25 26 void Solve() 27 { 28 for (int j=1;j<=m;j++) dp[1][j]=abs(b[j]-a[1]); 29 for (int i=2;i<=n;i++) 30 { 31 ll tmp=1ll<<60; 32 for (int j=1;j<=m;j++) 33 { 34 tmp=min(tmp,dp[i-1][j]); 35 dp[i][j]=abs(b[j]-a[i]); 36 dp[i][j]+=tmp; 37 38 } 39 } 40 for (int j=1;j<=m;j++) Ans=min(Ans,dp[n][j]); 41 } 42 43 int main() 44 { 45 //freopen("in.in","r",stdin); 46 //freopen("out.out","w",stdout); 47 48 scanf("%d",&n); 49 for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]=a[i]-i; 50 sort(b+1,b+n+1); 51 for (int i=1;i<=n;i++) if (i==1 || b[i]!=b[i-1]) b[++m]=b[i]; 52 53 Solve(); 54 printf("%I64d ",Ans); 55 56 return 0; 57 }