[关闭]
@ysner 2018-05-12T15:38:54.000000Z 字数 2797 阅读 1816

[APIO2009]采油区域

递推


题面

给出一个的矩阵。请在其中选择个互不相交的,大小恰为 的子矩阵,使得子矩阵的权值和最大。

解析

这题和CJOJ2501很像呢。。。
看到题,本能地打了一个然后至今调不出来。。。

解法一

矩阵对应端点为其右下方端点,即为其面积。
表示选择这个点对应矩阵,并且还选择个矩阵的最优解。
表示当前点可转移的上方所有点对应值最优值。表示前列中的最优矩阵
那么有
最巧妙的地方,我们最多可以选择3个矩阵,那么是不是可以看做选一个加上一个
表示当前点可转移的上方所有点对应值最优值。表示前列中的最优矩阵
那么有

  1. il void Matrix()
  2. {
  3. fp(i,1,n) fp(j,1,m) a[i][j]=gi()+a[i-1][j]+a[i][j-1]-a[i-1][j-1];//二维前缀和套路
  4. fp(i,k,n) fp(j,k,m) s[i][j]=a[i][j]+a[i-k][j-k]-a[i-k][j]-a[i][j-k];//以(i,j)为右下端点的k*k矩阵的面积(还是套路,自己画图就知道了)
  5. }
  6. il void Solve()
  7. {
  8. upmx=0;memset(lfmx,0,sizeof(lfmx));
  9. fp(i,k,n)
  10. {
  11. fp(j,k,m) upmx=max(upmx,s[i-k][j]);//i代表行,j代表列,该矩阵上面 底最下到该矩形的上边的矩形
  12. fp(j,k,m)
  13. {
  14. lfmx[j]=max(lfmx[j-1],lfmx[j]);//维护左边的最大权值矩形
  15. lfmx[j]=max(lfmx[j],s[i][j]);//维护上边的最大权值矩形
  16. f[i][j]=max(upmx,lfmx[j-k])+s[i][j];//累计合法情况
  17. }
  18. }//搞完两个矩阵的情况
  19. upmx=0;memset(lfmx,0,sizeof(lfmx));//lfmx变成维护f,f代表两个矩形,我们依据上面的套路继续选取s(1个)+f(2个)
  20. fp(i,k,n)
  21. {
  22. fp(j,k,m) upmx=max(upmx,f[i-k][j]);
  23. fp(j,k,m)
  24. {
  25. lfmx[j]=max(lfmx[j-1],lfmx[j]);
  26. lfmx[j]=max(lfmx[j],f[i][j]);
  27. ans=max(ans,max(upmx,lfmx[j-k])+s[i][j]);
  28. }
  29. }//搞完三个矩阵的矩阵
  30. //最后补充一句,在当前矩阵左上方选取的矩阵对当前矩阵没有影响
  31. }
  32. int main()
  33. {
  34. n=gi();m=gi();k=gi();
  35. Matrix();
  36. ans=0;
  37. Solve();
  38. printf("%d\n",ans);
  39. return 0;
  40. }

解法二

取三个互不相交的矩形?
何尝不是把整个图形分为三块,然后在每一块中取最大值?
分成三块有六种情况:
此处输入图片的描述
于是对应维护以每个点为右下角的矩形权值和。
据此,可以维护每个点左上、左下、右上、右下部分的权值和。
然后枚举中间点(两条直线的交线,或者中间矩形的右下角),不断取统计即可。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define max(a,b) (a>b?a:b)
  12. #define min(a,b) (a<b?a:b)
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int N=2100;
  17. int n,m,k,mp[N][N],a[N][N],b[N][N],c[N][N],d[N][N],ans;
  18. il int gi()
  19. {
  20. re int x=0,t=1;
  21. re char ch=getchar();
  22. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. int main()
  28. {
  29. n=gi();m=gi();k=gi();
  30. fp(i,1,n) fp(j,1,m) mp[i][j]=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]+gi();
  31. fq(i,n,k) fq(j,m,k) mp[i][j]-=(mp[i-k][j]+mp[i][j-k]-mp[i-k][j-k]);
  32. fp(i,k,n) fp(j,k,m) a[i][j]=max(mp[i][j],max(a[i-1][j],a[i][j-1]));
  33. fp(i,k,n) fq(j,m,k) b[i][j]=max(mp[i][j],max(b[i-1][j],b[i][j+1]));
  34. fq(i,n,k) fp(j,k,m) c[i][j]=max(mp[i][j],max(c[i+1][j],c[i][j-1]));
  35. fq(i,n,k) fq(j,m,k) d[i][j]=max(mp[i][j],max(d[i+1][j],d[i][j+1]));
  36. fp(i,k,n-k) fp(j,k,m-k) ans=max(ans,a[i][m]+c[i+k][j]+d[i+k][j+k]);
  37. fp(i,k,n-k) fp(j,k,m-k) ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]);
  38. fp(i,k,n-k) fp(j,k,m-k) ans=max(ans,a[n][j]+b[i][j+k]+d[i+k][j+k]);
  39. fp(i,k,n-k) fp(j,k,m-k) ans=max(ans,a[i][j]+b[n][j+k]+c[i+k][j]);
  40. fp(i,k,n-k) fp(j,k+k,m-k) ans=max(ans,a[n][j-k]+b[n][j+k]+mp[i][j]);
  41. fp(i,k+k,n-k) fp(j,k,m-k) ans=max(ans,a[i-k][m]+c[i+k][m]+mp[i][j]);
  42. printf("%d\n",ans);
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注