C221110C. SolarPea与网格
C221110C. SolarPea与网格
是怎么想到dp定义的？
思考下面这个情景：
- 如果一个人在 \(x\)， 另一个人在 \(y \ (x \lt y)\)， 那么在 \(x\) 的人会把 \(x \lt i \lt y\) 的所有 \(i\) 全走一遍，走完之后 \(x + 1 = y\)。
对于这个情景，我们想到记 \(f[i]\) 表示一个人在 \(i - 1\)，一个人在 \(i\) ，跳到终点后的max(前一个人得分 减去 后一个人得分)。
我们在转移时，先暂时忽略1，2两个点的贡献。最后加一个 \(a[1] - a[2]\) 就行。
答案： \(f[2]\)。
初始化：\(f[n] = 0\)。
\(n\) 是最后一步。因此 dp顺序 是\(n \sim i\) 。有转移：
解释一下：由于每次是前一个人先跳，所以他肯定想拿远处很大的一个数（现在不拿就会被对手拿），然后让对手把这一段全部拿掉。最后再把上一步的贡献加上，注意两个人的相对位置翻转了，所以是 \(- f[j]\) 而不是 \(+ f[j]\)。
这是最朴素的式子。
答案就是 \(f[2]\)。
考虑简化这个式子
我也不知道是怎么注意到可以这么优化的。。。（注意力惊人）
考虑把 \(j \gt i\) 的所有 \(j\) 分成两类：
-
\(j = i + 1\)， 则 \(f[i] = a[i + 1] - s[i] + s[i] - f[i + 1] = a[i + 1] - f[i + 1]\)。
-
\(j > i + 1\)， 则 \(f[i] = \max_{j \gt i + 1} a[j] - s[j - 1] + s[i] - f[j]\)。
又因为 \(f[i + 1] = \max_{j > i + 1} a[j] - s[j - 1] + s[i + 1] - f[j]\)。
两式相减，则 $f[i + 1] - f[i] = s[i + 1] - s[i] = a[i + 1] $。
则 \(f[i] = f[i + 1] - a[i + 1]\)。
综上：\(f[i] = |f[i+ 1] - a[i + 1]|\)。
考虑利用绝对值的一些性质
记 \(g[i]\) 表示当 \(a[n] = i\) 时，\(f_2 = g[i]\) 。
结合上面绝对值的式子，可以得到：
每增加一个绝对值，对 \(g[i]\) 的影响就是先整体向右平移 \(a[n]\)，然后 对于 \(i < a[n]\)， 按 \(y\) 轴对称一下。
发现不是很好直接做。考虑用 \(deque\) 维护，每次在把 \(<a[i]\) 的一段元素再插入队首即可。
值域只有 \(10^6\)， 可以直接维护。
如果 \(x\) 极大，那直接一步调到最后就可以（因为肯定最优）。
时间复杂度 \(O(\sum_a +q)\)。
/*
Think twice, code once
Please check the followings:
1.Array memory
2.Testing sentence
3.if_else condition
4.freopen
5.long long
*/
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
const int inf = 1e9;
list<int> g;
int n, q, cnt = 0;
int a[N], s[N], res[N * 10];
signed main(){
// freopen("test.in","r",stdin);
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
F(i, 1, n - 1) cin >> a[i], s[i] = s[i - 1] + a[i];
F(i, 0, s[n - 1] - s[2]) g.push_back(i);
F(i, 3, n - 1){
auto it = g.begin();
F(j, 1, a[i]) ++it, g.push_front(*it);//平移指针, 就相当于是平移图像了
}
for(auto x : g) res[++ cnt] = x;
cin >> q;
int x;
while(q --){
cin >> x;
if(x + 1 <= cnt) cout << res[x + 1] + a[1] - a[2] << '\n';
else cout << (x - s[n - 1] + s[2]) + a[1] - a[2] << '\n';
}
return 0;
}