离散化处理方法_索尼自动图像模式有什么用[通俗易懂]

Sonya was unable to think of a story for this problem, so here comes the formal description.
You are given the array containing n positive integers. At one turn you can pick any element and increase or decrease it by 1. The goal is the make the array strictly increasing by making the minimum possible number of operations. You are allowed to change elements in any way, they can become negative or equal to 0.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 3000) — the length of the array.
Next line contains n integer ai (1 ≤ ai ≤ 109).

Output

Print the minimum number of operation required to make the array strictly increasing.

Examples

Input
7
2 1 5 11 5 9 11
Output
9
Input
5
5 4 3 2 1
Output
12

Note

In the first sample, the array is going to look as follows:
2 3 5 6 7 9 11
|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9
And for the second sample:
1 2 3 4 5
|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12

题目大意：给你n个数，你每次可以将任意一个数加一或者减一。问至少要操作几次，才能让这n个数单调递增。输出最小的操作次数。

题目分析：
方法一：

1. 预处理：因为a[i]的范围是1到1e9，如果直接dp序列严格递增，那么dp就得从1循环到1e9，这样无论是在空间还是时间上都是不允许的。
   1） 然而我们可以通过a[i]-=i这步操作，将序列转化为非严格递增序列，那么答案就可以在给定序列中找到，因为把一串数都变成相等的数时，最优解一定是变成他们的中位数，而中位数一定是存在于原有数中的，
   2）再将这n个数进行离散化处理，(离散化处理：可以用b[]存储给定序列a[]-=i的数，并进行排序)，这样dp就最多只需要从1循环到n,那么时间复杂的就优化到了O(n^2)。
2. 状态表示：f[i][j] //表示前i个数，这i个数进行操作后最大的数不超过b[j] 的操作次数的最小值(b[]即为离散化后的序列)
3. 状态计算：有两种方法得到可以得到f[i][j]
   1)当将第i个数操作后为b[j]时，f[i][j]为f[i-1][j]+abs(a[i]-b[j])。
   2)当将第i个数操作后值小于b[j]时，f[i][j]为min(f[i][k])(1<= k < j)。这样的话时间复杂度就变成了O(n^3)。不过在这里我们可以用一个优化操作:即让f[i][j]为f[i][j-1],因为虽然每次只是求了f[i][j-1],但因为前面的f[i][1-j-1]都求得了最小值，因此只需要算出前面一个的即可。
   因此，状态转移方程为：f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-b[j])).

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#define LL long long
using namespace std;
const int N=3005;
int a[N],b[N];
LL f[N][N];      //答案有可能爆int
int main()
{ 
   
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)   //预处理+离散化
	{ 
   
	    cin>>a[i];
	    a[i]-=i;
	    b[i]=a[i];
	}
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)
	{ 
   
		f[i][0]=1e18;      //初始化，因为当j为1时，只有1）这一种状态
		for(int j=1;j<=n;j++)
		{ 
      //状态计算：即两种状态取一个最小值
		    f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-b[j]));
		}
	}
	LL ans=1e18;
	for(int i=1;i<=n;i++)   //答案为f[n][i]中的一个，要遍历寻找最小值
	{ 
   
		ans=min(ans,f[n][i]);
	}
	cout<<ans<<endl;
	return 0;
}

方法二：
上面用动态规划的方法求解的时间复杂的为O(n^2)。我们也可以用数学的方法来进行求解，时间复杂度为O(n logn).
具体原理是啥我还没弄明白。。。。。。
先把代码放上：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#define LL long long
using namespace std;
const int N=3e3+5,mod=1e9+7;
priority_queue<int>q;
int main()
{ 
   
	int n;
	LL ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{ 
   
		int x;
		cin>>x;
		x-=i;
		q.push(x);
		int max=q.top();
		if(max>x)
		{ 
   
			ans+=max-x;
			q.pop();
			q.push(x); 
		}
	}
	cout<<ans<<endl;
	return 0;
}

今天的文章离散化处理方法_索尼自动图像模式有什么用[通俗易懂]分享到此就结束了，感谢您的阅读。