P10086

本题是一道典型的动态规划初步题，但是一打开算法标签，就发现这题做法特多：

线段树、单调队列、动规、树状数组……

作为一个蒟蒻，我毫不犹豫地选择了最简单的做法：动规

这题很水，题目把计算距离值的式子给你了。分析题目可知:

$fa_i = \max(fa[i-1],d[i])$

$fb_i = \max(fb[i+1],d[i])$

得出状态转移方程，本题解法自然水落石出了。

其实这题难度并不高，关键在于细节（正是这些细节把我坑了一个小时）。

警钟敲烂：

• 不能直接取余 $1e9$，因为 $1e9$ 表示 $1.0\times 10^9$，是实数类型。
• 数组要开足够大，至少 $10^7$,不然就RE，只能拿 $62$ 分。

话不多说，上代码！

Code：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9;//注意细节
long long n,f,d[10000010],a[10000010],b[10000010],m,x,y,z;
int main() {
	cin >> n >> f;
	if (f == 1){
		for (int i=1;i<=n;i++) cin >> d[i];
		for (int i=n+1;i<=2*n;i++) d[i]=d[i-n];//注意此处需要转换一下d[i]
	} else if (f == 2) {
		cin >> m >> x >> y >> z;
		for (int i = 1;i <= m;i++) cin >> d[i];
		for (int i = m + 1;i <= n;i++) d[i] = (x * d[i-2] + y * d[i-1]+z) % mod+1;//题目的距离公式
	}
   //虽说代码不短，但到这里为止都是输入                            
	a[0] = b[n+1] = -1e18;
	for (int i=1;i<=n;i++){
		d[i] -= i;
		a[i] = max(a[i-1],d[i]);
	}
	for (int i = n;i >= 1;i--) b[i] = max(b[i+1],d[i]);//本题需要两个解，因此定义两个动规数组
	long long ans = 1e18,pos = 0;
	for (int i=1;i<=n;i++){
		int p = max(b[i] + i,a[i-1] + i - n);
		if (p < ans) {
			ans = p;
			pos = i;
		}
	}
	cout << ans << ' ' << pos;
	return 0;
  //完结撒花~
}

求管理员审核通过~