道路游戏
给定一个长度为 \(n\) 的环,每条边每个时刻都有对应的价值,经过即得到。
每个时刻如果没有在运动,就可以任意选择起点和持续运动时间,每次运动将移动一条边的长度。
对于选择的起点 \(i\) 需要减去 \(a_i\) 的价值,\(a_i\) 不随时间变化改变。
求最终价值的最大值,有可能为负。
\(f(i)\) 表示第 \(i\) 个时刻的 \(\max\)。\(g(i,j)\) 位置 \(i\) 时间 \(j\) 斜线上的前缀和。
\(f(i)=\max\limits_{0<j<n,1\leq k\leq p}\{f(i-k)+g(j-1,i)-g(j-k-1,i-k)-a(j-k)\}\)
这样可以做到 \(O(n^3)\),需要追求优化。
设 \(h(i,j)=f(i)-g(j-1,i)-a(j)\)
\(f(i)=\max\limits_{0<j<n,1\leq k\leq p}\{h(i-k,j-k)+g(j-1,i)\}\)
相当于是斜线上的单调队列,至于队列编号的钦定...,不妨定为 \((i-j+1)\mod n\)。
这样钦定的原因是,第一行的队列编号就是 \(0\sim n-1\),比较优美。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; const int INF = 1e9; int n, m, p; int f[N], a[N], g[N][N]; int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define MP make_pair #define V first #define P second typedef pair<int, int> PII; struct Queue{ int l, r; PII q[N]; void Init(){l = 1, r = 0;} int Front(){return q[l].V;} void Push(int i, int val){ while(l <= r && q[r].V <= val) r --; q[++ r] = MP(val, i); } void Pop(int limit){ while(l <= r && q[l].P < limit) l ++; } } Q[N]; int Get(int i, int j){return ((i - j) + 2 * n) % n;} int main(){ n = read(), m = read(), p = read(); for(int i = 0; i < n; i ++) for(int j = 1; j <= m; j ++) g[i][j] = read(); for(int i = 0; i < n; i ++) a[i] = read(); for(int j = 2; j <= m; j ++) for(int i = 0; i < n; i ++) g[i][j] += g[Get(i, 1)][j - 1]; for(int i = 0; i < n; i ++){ int k = (i == n - 1) ? 0 : i + 1; Q[k].Init(); Q[k].Push(0, - a[i]); } for(int i = 1; i <= m; i ++) f[i] = - INF; for(int i = 1; i <= m; i ++){ for(int j = 0; j < n; j ++){ int k = Get(j, i - 1); Q[k].Pop(i - p); f[i] = max(f[i], Q[k].Front() + g[Get(j, 1)][i]); } for(int j = 0; j < n; j ++) Q[Get(j, i - 1)].Push(i, f[i] - g[Get(j, 1)][i] - a[j]); } printf("%d\n", f[m]); return 0; }