DP两道关于递增非递增的题目

POJ - 3666 

首先我们会发现，最终修改后，或者和前一个数字一样，或者和后一个数字一样，这样才能修改量最小。

不严格递减最后修改完成后的各个数一定是原序列中的某一个数

这个大概可以这么理解：原序列，从左到右扫过去，如果左边的大于右边的，要嘛左边的减掉使其等于右边的，要嘛右边的加上使其等于左边的。

那个思路是这样：dp[i][j] = min(dp[i-1][k])+a[i]-b[j], 1<=k<=j。dp[i=当前考虑的前i个数][j=第i个数在总序列中排第j小]=当前的情况的最小改动量。什么意思呢，就是求当前dp[i][j]时候，考虑前i-1个数字，取第i-1个数字在第k（k=1…j）小中的最小改动量，再加上第i个数字成为第j小的改动量。

#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=2010; int n; int a[N]; int b[N]; int dp[N][N]; int main() { int i,j,k,ans; cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) b[i]=a[i]; sort(b+1,b+1+n,cmp); for(j=1;j<=n;j++){ dp[1][j]=a[1]-b[j]; if(dp[1][j]<0) dp[1][j]=-dp[1][j]; } for(i=2;i<=n;i++) // 非严格递增 { k=dp[i-1][1]; for(j=1;j<=n;j++) { k=min(dp[i-1][j],k);//这里k是用来维护1~k（j）中最小的dp[i][j]的 dp[i][j]=k+abs(a[i]-b[j]); //dp[i][j] = min{dp[i - 1][0...j] + ?abs(a[i] - b[j])} } } ans=dp[n][n]; for(i=n;i>=1;i--) ans=min(ans,dp[n][i]); printf("%d\n",ans); return 0; }

 Sonya and Problem Wihtout a Legend

 CodeForces - 713C  就变了一下，用了什么公式

就把单调递增变为非单调递增了 #include <cstdio>  #include <algorithm>  #include <iostream>  using namespace std;  int a[3100],b[3100];  long long dp[3100][3100];  int main()  {      int n;      scanf("%d",&n);      for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=i,b[i]=a[i];      sort(b+1,b+1+n);        for(int i=1;i<=n;i++)      {          long long mn=dp[i-1][1];          for(int j=1;j<=n;j++)          {              mn=min(mn,dp[i-1][j]);              dp[i][j]=mn+abs(a[i]-b[j]);          }      }      long long ans=dp[n][1];      for(int i=2;i<=n;i++) ans=min(ans,dp[n][i]);      cout<<ans;      return 0;  }