你可能是写错了,我用rmq解的原理与单调队列差不多
by X_o_r @ 2017-09-13 21:29:42
```cpp
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
inline void read(int &Res){
char ch=getchar();
for (Res=0;!isdigit(ch);ch=getchar());
for (;isdigit(ch);ch=getchar()) Res=(Res<<3)+(Res<<1)+ch-48;
}
int n,m,p,A[1024][1024],F[1024],C[1024],stk[1024][1024],ch[1024][1024][2],top[1024],root[1024],G[1024][1024];
inline void Update(int id,int now){
while (top[id]&&G[id][stk[id][top[id]]]<=G[id][now]) ch[id][now][0]=stk[id][top[id]--];
ch[id][stk[id][top[id]]][1]=now,stk[id][++top[id]]=now;
root[id]=stk[id][1];
}
inline int Query(int id,int L,int R){
for (int x=root[id];x;x=ch[id][x][x<=R]) if (L<=x&&x<=R) return G[id][x];
}
int main(){
read(n),read(m),read(p),memset(F,192,sizeof F),F[0]=0;
for (int i=0;i<n;i++)
for (int j=1;j<=m;j++) read(G[i][j]);
for (int i=0;i<n;i++) read(C[i]),A[1][i]=G[i][1];
for (int i=1;i<=m;i++)
for (int j=0;j<n;j++) A[i][j]=A[i-1][(j+n-1)%n]+G[j][i];
for (int i=1;i<=m;i++)
for (int j=0,k;j<n;j++) G[k=(i-j+n)%n][i]=F[i-1]-A[i-1][(j+n-1)%n]-C[j],Update(k,i),F[i]=max(F[i],A[i][j]+Query(k,max(i-p+1,1),i));
printf("%d",F[m]);
return 0;
}
要建n个单调队列
```
by X_o_r @ 2017-09-13 21:31:54
是有的
可以找规律,
最后可以斜着DP, 复杂度O(n^2)
@Super\_Nick
by 重回巅峰! @ 2017-09-19 19:41:47