首页 > 代码库 > Making the Grade(POJ3666)
Making the Grade(POJ3666)
题目大意：
给出长度为n的整数数列,每次可以将一个数加1或者减1,最少要多少次可以将其变成单调增或者单调减(不严格).
题解：
1.一开始我有一个猜想,就是不管怎么改变,最终的所有数都是原来的某个数。然而我并不会证明,然而我属于那种不彻底弄清楚就不会去写的那种顽固分子,于是就脱了好几天。网络上有很多关于此题的题解,确实用了这个猜想来离散化,但是都是讲怎么dp,然后最后扯一句“由于数据比较大,可以离散化”之类的话,要么就是相当粗略的证明(也许已经说的够清楚了只不过我没理解...)。
2.今天早上起来洗漱的时候,感觉头脑比较清醒,再次想了一下这个问题,想到一个自认为正确的证明：
记原来的数从小到大排序后分别是$a_1\ a_2\ a_3\cdots a_n$ 修改后从左到右分别是$b_1\ b_2\ b_3\cdots 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。
代码：
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 first13 #define Y second14 #define Mod 100000000715 #define N 301016 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\n",Ans);55 56 return 0;57 }
Making the Grade(POJ3666)