CF1304F2 Animal Observation (hard version)

一、题目

点此看题

二、解法

哈哈哈，我竟然自己做出来了（好像并没有什么值得骄傲的 ? ）

首先朴素 $dp$，设 $dp[i][j]$为考虑到了第 $i$天，选择在 $j$处设一个 $[j,j+k-1]$的观察点，所得到的最大观察数量。转移枚举上一天设置的观察点，注意判断两个区间有相交的情况只能算一次。

转移的话维护一个单调队列，从左到右，从右到左按道理都要更新一遍，这里只讲从左到右。这里需要用到全局标记，也就是在 $j$移动向 $j+1$的过程中所有和 $j$相交的区间贡献都要加上 $a[i][j]$，就更新这个单调队列的标记，对于已经不相交的就直接弹出，记录一下弹出的最大值即可。

另一种情况学懂了就能推出来，时间复杂度 $O(nm)$

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 55;
const int M = 20005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,m,k,ans,q[M],g[M],a[N][M],s[N][M],dp[N][M];
signed main()
{n=read();m=read();k=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){a[i][j]=read();s[i][j]=s[i][j-1]+a[i][j];}for(int i=1;i<=m-k+1;i++)dp[1][i]=s[1][i+k-1]-s[1][i-1];for(int i=2;i<=n;i++){int h=1,t=0,tag=0,p=0;for(int j=1;j<=m-k+1;j++){while(h<=t && q[h]<=j-k) {p=max(p,g[h]+tag);h++;}while(h<=t && g[t]<=dp[i-1][j]-tag) t--;q[++t]=j;g[t]=dp[i-1][j]-tag;dp[i][j]=max(g[h]+tag,p)+s[i][j+k-1]-s[i][j-1];tag+=a[i][j];}h=1;t=tag=p=0;for(int j=m-k+1;j>=1;j--){while(h<=t && q[h]>=j+k) {p=max(p,g[h]+tag);h++;}while(h<=t && g[t]<=dp[i-1][j]-tag) t--;q[++t]=j;g[t]=dp[i-1][j]-tag;dp[i][j]=max(dp[i][j],max(g[h]+tag,p)+s[i][j+k-1]-s[i][j-1]);tag+=a[i][j+k-1];}}for(int i=1;i<=m-k+1;i++)ans=max(ans,dp[n][i]);printf("%d\n",ans);
}