题意:给出n,和m表示有n天,m块区域,每块区域都有一定数论的动物数量,k表示可以在这一天中观察[x,max(x+k-1,m)]的区域内的动物,有俩台相机,一台只能在偶数天用,另一台则是在奇数天用,每用一次就得在那个区域内待俩天,相邻的要是有重复的区域,该区域内的动物数只计数一次,问最多有可能的动物数目是多少
分析:因为n<=50,m<=20000,所以我们考虑一下dp[n][m],dp[i][j]表示:在第 i 天选择[j,j+k-1]区域拍摄的最大拍摄量。
因为是连续拍摄俩天,所以我们可以想象一个块,这个块的大小是:2*k(2为连续拍摄俩天,k为连续的区域),然后第 i 天转移的过程就是这个块滑块的过程,下面考虑第 i 天;
因为会涉及重复的问题,所以我们不妨直接把这个块全部算成都有效的块,然后这个块要和 (前一天的dp (减去这个块对这个前一天的dp)的影响) 相加才为选择这个区域来拍摄的最优值;
接下来的dp就相当于这个块在第 i 天的dp数组上进行“滑块”,假设当前这个块(左上角为dp[i][j],dp[i+1][j+k-1])向右 “滑” ,那么就考虑加入[j+k]区域的动物对dp[i-1][]的影响和去掉 [j] 区域对dp[i-1][]的影响;
这个影响靠线段树的区间加,区间最值来维护,详细可以看代码注释
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r const int M=2e4+4; const int N=55; int sum[N][M],a[N][M],dp[N][M]; struct node{ int lazy,val; }tr[M<<2]; void build(int root,int l,int r){ if(l==r){ tr[root].lazy=tr[root].val=0; return ; } int midd=(l+r)>>1; build(lson); build(rson); } void pushdown(int root){ int x=tr[root].lazy; tr[root<<1].lazy+=x; tr[root<<1|1].lazy+=x; tr[root<<1].val+=x; tr[root<<1|1].val+=x; tr[root].lazy=0; } void up(int root){ tr[root].val=max(tr[root<<1].val,tr[root<<1|1].val); } void update(int L,int R,int c,int root,int l,int r){ if(L<=l&&r<=R){ tr[root].lazy+=c; tr[root].val+=c; return ; } int midd=(l+r)>>1; if(tr[root].lazy) pushdown(root); if(L<=midd) update(L,R,c,lson); if(R>midd) update(L,R,c,rson); up(root); } int query(int L,int R,int root,int l,int r){ if(L<=l&&r<=R){ return tr[root].val; } if(tr[root].lazy) pushdown(root); int res=0; int midd=(l+r)>>1; if(L<=midd) res=max(res,query(L,R,lson)); if(R>midd) res=max(res,query(L,R,rson)); up(root); return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; sum[i][j]=sum[i][j-1]+a[i][j]; } } ///预处理dp[1]的情况 for(int j=1;j<=m-k+1;j++){ dp[1][j]=sum[1][j+k-1]-sum[1][j-1] +sum[2][j+k-1]-sum[2][j-1]; } for(int i=2;i<=n;i++){ memset(tr,0,sizeof(tr)); for(int j=1;j<=m;j++) update(j,j,dp[i-1][j],1,1,m); for(int j=1;j<=k;j++)///算一个小预处理 ,为第一个窗口计算做准备 update(1,j,-a[i][j],1,1,m); ///枚举每一个窗口 for(int j=1;j<=m-k+1;j++){///每个窗口为上一个窗口向右移动一格,代价为去掉左边一个增加右边一个对答案的贡献 dp[i][j]=max(dp[i][j],query(1,m,1,1,m)+sum[i][j+k-1]-sum[i][j-1] +sum[i+1][j+k-1]-sum[i+1][j-1]); update(max(1,j-k+1),j,a[i][j],1,1,m);///减去左边出队的 update(j+1,j+k,-a[i][j+k],1,1,m);///加上右边入队的 } } int ans=0; for(int j=1;j<=m;j++) ans=max(ans,dp[n][j]); cout<<ans<<endl; return 0; }View Code