题目大意
给定一个序列,现在有两种操作,
一种是使序列中某一个数加一,一种是使其减一.
问把这个序列弄成单调递增的最少操作次数是多少.
题目分析
这题我是看题解的,发现是蛮经典的一道题.
首先考虑不降序列,那么我们如果暴力DP那么数据范围
是九次方存不下,我们需要找到一种可以包含所有可能转移到的状态的
空间而使空间开的下.
我们可以证明序列最后映射成的,是其原本序列的子集.
首先可以肯定的是至少有一个数是不用变的,那么从这个数开始,
对于这个数,设为x,假设下一个数小于x,那么很显然结论可以延扩下去,
如果是大于,可能存在一种情况是两个数各走一些步数来到达一个不归于
序列集合的一个数来达到目的,可以证明这种情况的话那么下面的数肯定是在这个目的数的
上方否则明显存在更优解,如果这个目的数在两者之间可以用一个不差的策略替换即两数都归为
下一个数值.
口胡了那么久,太严格证明本弱又不会,,想到哪里说到哪里吧,仅供参考.
不减的情况我们完成了,对于递增的情况有个技巧就是把a数组减去其对应的序号,
详见代码,这样任意原序列的不减在变化后的序列中都是单调的了.
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=3e3+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);
}
/*
题目大意:
给定一个序列,现在有两种操作,
一种是使序列中某一个数加一,一种是使其减一.
问把这个序列弄成单调递增的最少操作次数是多少.题目分析:
这题我是看题解的,发现是蛮经典的一道题.
首先考虑不降序列,那么我们如果暴力DP那么数据范围
是九次方存不下,我们需要找到一种可以包含所有可能转移到的状态的
空间而使空间开的下.
我们可以证明序列最后映射成的,是其原本序列的子集.
首先可以肯定的是至少有一个数是不用变的,那么从这个数开始,
对于这个数,设为x,假设下一个数小于x,那么很显然结论可以延扩下去,
如果是大于,可能存在一种情况是两个数各走一些步数来到达一个不归于
序列集合的一个数来达到目的,可以证明这种情况的话那么下面的数肯定是在这个目的数的
上方否则明显存在更优解,如果这个目的数在两者之间可以用一个不差的策略替换即两数都归为
下一个数值.
口胡了那么久,太严格证明本弱又不会,,想到哪里说到哪里吧,仅供参考.不减的情况我们完成了,对于递增的情况有个技巧就是把a数组减去其对应的序号,
详见代码,这样任意原序列的不减在变化后的序列中都是单调的了.
*/
ll n,a[maxn],b[maxn],dp[maxn][maxn];
int main(){cin>>n;rep(i,1,n+1) {cin>>a[i];b[i]=(a[i]-=i);}sort(a+1,a+1+n);mst(dp,0);rep(i,1,n+1){ll minv=1e18;rep(j,1,n+1){minv=min(minv,dp[i-1][j]);dp[i][j]=minv+abs(b[i]-a[j]);}}ll ans=1e18;rep(i,1,n+1) ans=min(ans,dp[n][i]);cout<<ans<<"\n";return 0;
}