题解 P1070 【道路游戏】
dengyaotriangle
·
·
题解
这里提供一个很巧的想法
非常好理解，也非常妙
这道题的O(n^3)dp很显然，如果不会的话先看其它题解
而如何优化到O(n^2)或O(n^2logn)过掉本题就有意思了
首先观察到这个机器人在动就很烦人，我们要想办法把它定住。
那咋整啊，众所周知运动是相对的，所以我们可以让工厂的代价，和金币随着时间逆时针旋转，这样就等价于机器人顺时针旋转
那么显然，现在第i个工厂第j时刻的代价是 c[(i+j+2)\%n\ +1]，而第i条路上第j时刻的金币数是 a[(i+j+2)\%n\ +1][j] ，其中c[i]为原输入中第i个工厂的代价，a[i][j]为原输入中第i条路第j单位时间的金币数
那么问题转化为
每次花一定的代价在一个地方放机器人，最多维持p单位时间，每单位时间机器人都会捡起自己右边道路上的金币，机器人不动
那么我们朴素的列一个dp方程
dp[i]=\max_{j=1}^{n}\max_{k= max(0,i-p)}^{i-1} dp[k]+pfx[j][i]-pfx[j][k]-cost[j][k+1]
其中$cost[i][j]$代表第$i$个工厂第$j$单位时间的代价（注意我们转动了它，所以虽然原题中不变这里也是变化的）
$pfx[i][j]$代表$\sum_{k=1}^{j} val[i][k]$，$val[i][j]$代表第$i$条路第$j$秒的金币数
### 注意上述的都是转化后的值
**所以dp方程的意义是：枚举所以可能的上次选的工厂和时间，然后取max**
显然这个dp是$O(n^3)$的
那么如何优化？
我们做一个简单的变形
$$ dp[i]=\max_{j=1}^{n}\max_{k= max(0,i-p)}^{i-1} dp[k]+pfx[j][i]-pfx[j][k]-cost[j][k+1]$$
$$ =\max_{j=1}^{n} pfx[j][i]+\max_{k= max(0,i-p)}^{i-1} dp[k]-pfx[j][k]-cost[j][k+1]$$
设$g[j][k]=dp[k]-pfx[j][k]-cost[j][k+1]$，则
$$ =\max_{j=1}^{n} pfx[j][i]+\max_{k= max(0,i-p)}^{i-1} g[j][k]$$
其中$\max_{k= max(0,i-p)}^{i-1} g[j][k]$，可以开$n$个优先队列/单调队列，然后参见[滑动窗口的50分或100分解法](https://www.luogu.org/problemnew/show/P1886)，来实现单次询问$O(1)$或$O(logn)$，均可通过此题
注意这里是一边求值一边询问最大值的，故不能用st表。
个人认为优先队列更好写，如果时间复杂度以及常数允许的话尽量写优先队列，减少写挂的概率
**注意答案有可能有负数，dp初始值需设为0xc0c0c0c0（约等于-1e9）**
参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,p;
int a[maxn][maxn],r[maxn][maxn];
int c[maxn];
int pfx[maxn][maxn];
priority_queue<pair<int,int> > q[maxn];
bool operator<(pair<int,int> a,pair<int,int> b){
if(a.first==b.first) return a.second>b.second;
return a.first<b.first;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>p;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
r[j][i]=a[(j+i-2)%n+1][i];
}
}
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) pfx[i][j]=pfx[i][j-1]+r[i][j];
}
for(int i=1;i<=n;i++){
q[i].push(make_pair(-c[(i-1)%n+1],0));
}
int ans=0xc0c0c0c0;
for(int i=1;i<=m;i++){
int mx=0xc0c0c0c0;
for(int j=1;j<=n;j++){
int cur=pfx[j][i];
while(q[j].top().second<i-p) q[j].pop();
cur+=q[j].top().first;
mx=max(mx,cur);
}
for(int j=1;j<=n;j++){
q[j].push(make_pair(mx-pfx[j][i]-c[(j+i-1)%n+1],i));
}
ans=max(ans,mx);
}
cout<<ans;
return 0;
}
```