Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。
但是不希望改变过多的数，也不希望改变的幅度太大。
solution
正解：DP 这题相当诡异. 首先是一个套路，转化严格递增为不降，我们只需要把序列中的每一个元素都变为 \(a[i]-i\)，设新数组为 \(b[i]\). 我们要改变的尽量少，就要使得不改变的尽量多，设 \(f[i]\) 表示前\(i\)个已经改变好，不改变数的最小值. 原数组 \(a[i]\) 的话，转移为 \(f[i]=Max(f[j]+1)\)，需要满足 \(a[i]-a[j]>=i-j\). 对于新数组，我们只需要满足不降即可，所以 \(b[j]<=b[i]\)，那么第一问我们可以转化为最长不降子序列，\(O(nlogn)\) 可以求出
对于第二问，我们设 \(g[i]\) 表示前\(i\)已经处理好的最小费用，\(g[i]=g[j]+w[j+1][i]\)，\(j\) 满足 \(f[i]=f[j]+1\)，我们可以挂链转移 我们需要猜一个结论：\(w[j][i]\) 的最优情况一定是存在一个 \(k\) \(i<k<j\) 使得 \(j-k\) 全部变为 \(b[j]\)，\(i-k\)全部变为 \(b[i]\). 可以感性证明：前面的要选的位置尽量低，因为如果前面的选的很高，那么后面的一堆都要变化这么多，显然不会更优. 我们枚举断点转移即可，复杂度 \(O(n^3)\) 但是随机数据下跑得过，十分玄学
#include#include #include #include #include #include #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;typedef long long ll;const int N=35005;const ll inf=2e16;ll a[N];int n,f[N];ll h[N];ll g[N],s1[N],s2[N];il int midit(RG int l,RG int r,ll x){ RG int mid,ret=0; while(l<=r){ mid=(l+r)>>1; if(h[mid]<=x)ret=mid,l=mid+1; else r=mid-1; } return ret;}void solve1(){ int t; a[++n]=1<<30; for(int i=1;i<=n;i++)h[i]=2e9+10; h[1]=a[1];f[1]=1; for(int i=2;i<=n;i++){ t=midit(1,n,a[i]); f[i]=t+1; h[f[i]]=Min(h[f[i]],a[i]); } printf("%d\n",n-f[n]);}int num=0,head[N],to[N],nxt[N];il void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}void solve2(){ for(int i=n;i>=0;i--)link(f[i],i),g[i]=inf; g[0]=0;a[0]=-a[n]; for(int i=1;i<=n;i++){ for(int l=head[f[i]-1];l;l=nxt[l]){ int j=to[l];if(j>i)break; if(a[j]>a[i])continue; for(int k=j;k<=i;k++){ s1[k]=abs(a[j]-a[k]); s2[k]=abs(a[i]-a[k]); } for(int k=j+1;k<=i;k++) s1[k]+=s1[k-1],s2[k]+=s2[k-1]; for(int k=j;k