「BZOJ1177」[Apio2009] Oil
Description
采油区域 Siruseri政府决定将石油资源丰富的Navalur省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域，被划分为M×N个小块。 Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示为M×N个非负整数，即对每一小块土地石油储量的估计值。 为了避免出现垄断，政府规定每一个承包商只能承包一个由K×K块相连的土地构成的正方形区域。 AoE石油联合公司由三个承包商组成，他们想选择三块互不相交的K×K的区域使得总的收益最大。 例如，假设石油储量的估计值如下： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9 如果K = 2, AoE公司可以承包的区域的石油储量总和为100, 如果K = 3, AoE公司可以承包的区域的石油储量总和为208。 AoE公司雇佣你来写一个程序，帮助计算出他们可以承包的区域的石油储量之和的最大值。
Input
输入第一行包含三个整数M, N, K，其中M和N是矩形区域的行数和列数，K是每一个承包商承包的正方形的大小（边长的块数）。接下来M行，每行有N个非负整数表示这一行每一小块土地的石油储量的估计值
Output
输出只包含一个整数，表示AoE公司可以承包的区域的石油储量之和的最大值。
Sample Input
12 12 3
2 3 2 3 3 3 3 2 3 3 2
3 3 3 2 2 3 3 4 2 2 3
3 4 3 4 2 3 4 3 4 3 2
4 4 4 5 3 2 4 4 4 3 3
4 5 3 3 6 6 6 3 5 2 3
5 5 4 5 5 6 6 4 5 3 2
3 4 2 3 6 7 6 3 3 3 3
2 3 3 3 2 2 2 2 3 4 3
2 2 4 3 4 3 2 3 3 2 4
3 3 3 3 2 4 3 3 3 2 3
2 3 2 3 4 4 3 3 2 3 2
3 3 3 3 3 3 4 2 3 4 3
2 3 2 3 3 3 3 2 3 3 2
3 3 3 2 2 3 3 4 2 2 3
3 4 3 4 2 3 4 3 4 3 2
4 4 4 5 3 2 4 4 4 3 3
4 5 3 3 6 6 6 3 5 2 3
5 5 4 5 5 6 6 4 5 3 2
3 4 2 3 6 7 6 3 3 3 3
2 3 3 3 2 2 2 2 3 4 3
2 2 4 3 4 3 2 3 3 2 4
3 3 3 3 2 4 3 3 3 2 3
2 3 2 3 4 4 3 3 2 3 2
3 3 3 3 3 3 4 2 3 4 3
Sample Output
119
题解
http://trinklee.blog.163.com/blog/static/238158060201482371229105/
re不停之后发现。。。
数据有问题，快速读入呵呵了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000000000LL #define pa pair<int,int> #define ll long long #define N 2505 #define fp(a,b,c) for(int a=b;a<=c;a++) #define fd(a,b,c) for(int a=c;a>=b;a--) using namespace std; int n,m,K,ans; int a[N][N],b[N][N],c[N][N],d[N][N],s[N][N]; int main() { scanf("%d%d%d",&n,&m,&K); fp(i,1,n)fp(j,1,m) { int x;scanf("%d",&x); s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x; } fd(i,K,n)fd(j,K,m)s[i][j]-=s[i-K][j]+s[i][j-K]-s[i-K][j-K]; fp(i,K,n)fp(j,K,m)a[i][j]=max(s[i][j],max(a[i-1][j],a[i][j-1])); fp(i,K,n)fd(j,K,m)b[i][j]=max(s[i][j],max(b[i-1][j],b[i][j+1])); fd(i,K,n)fp(j,K,m)c[i][j]=max(s[i][j],max(c[i+1][j],c[i][j-1])); fd(i,K,n)fd(j,K,m)d[i][j]=max(s[i][j],max(d[i+1][j],d[i][j+1])); fp(i,K,n-K)fp(j,K,m-K)ans=max(ans,a[i][j]+b[i][j+K]+c[i+K][m]); fp(i,K,n-K)fp(j,K+K,m)ans=max(ans,b[i][j]+d[i+K][j]+a[n][j-K]); fp(i,K+K,n)fp(j,K,m-K)ans=max(ans,c[i][j]+d[i][j+K]+a[i-K][m]); fp(i,K,n-K)fp(j,K,m-K)ans=max(ans,a[i][j]+c[i+K][j]+b[n][j+K]); fp(i,K,n)fp(j,K+K,m-K)ans=max(ans,s[i][j]+a[n][j-K]+b[n][j+K]); fp(i,K+K,n-K)fp(j,K,m)ans=max(ans,s[i][j]+a[i-K][m]+c[i+K][m]); printf("%d\n",ans); return 0; } |
计数器 9854032
OI 课件=>
OI 课件=>
无限re。。。。。。
求问数据有什么问题……
黄学长，您的样例为啥每行只有11个数？