题面
有一个矩形区域被划分为N行M列的网格,每个格子里有一定数量的资源并记录在矩阵val中,坐标(x,y)位置上资源量为val[x][y],其val中每个元素的值为0~9的整数。如果你在某个网格(a,b)上造一座保护塔,那么你可以占领K个网格中的资源,这K个格子分别是(a+dx[1],b+dy[1]),(a+dx[2],b+dy[2]),...,(a+dx[K],b+dy[K]),注意(a,b)这格本身可能未必会被占领。现在你能建造不超过2个塔,问最多能占领多少资源?一个网格被多个塔占领时其资源只计算一次。另外如果计算的位置(a+dx[i],b+dy[i])在网格外,则不贡献任何资源。
Input
多组测试数据,第一行一个整数T,表示测试数据数量,1<=T<=5
每组测试数据有相同的结构构成:
每组数据第一行三个整数N,M,K,其中2<=N,M<=100,1<=K<=10。
之后会有N行,每行M个元素,表示val矩阵。每个元素为0~9,占一个字符,元素间没空格。
再接下来有K行,每行两个整数dx[i]与dy[i],其中-(N-1)<=dx[i]<=N-1,-(M-1)<=dy[i]<=(M-1).
分析
首先肯定2个炮台都要建的,但是 n*m*k=1e5,为什么不暴力枚举在每个点呢?哦,需要枚举2个点。。那就是1e10了。
用数据结构优化一下?是放在线段树专题的题,然而实在看不出来用线段树维护啥啊??
机房julao稍微点拨了一下,我在重整了一下思路。如果没有每个点的贡献只能出现一次的话,就直接枚举每个点找次大和最大值了。
但是有了这个限制,然而有一句话,你爸爸始终是你爸爸【雾
所以即便是最大和次大有重复的点,相对来说,它们还是更大的,至少你要权值较大,你才能可能成为被选的点之一。
于是我们就不止用最大和次大,还得算3大,4大……这些组合起来的总贡献,反正不超时的情况下,尽量多选一些点来试一试。优先队列维护一下。
理是这个理,但是稍微设计一下数据就好容易被卡掉qvq。不过真的是个可爱的暴力呢
代码
#include<bits/stdc++.h> using namespace std; #define N 110 int t,n,m,k,tot,ans; int dx[N],dy[N],a[N][N],vis[N][N]; char s[N]; struct email { int x,y,v; }; bool operator <(email q1,email q2) { return q1.v<q2.v; } priority_queue<email>q; inline email mp(int x,int y,int v){email c;c.x=x,c.y=y,c.v=v;return c;} inline void init(){memset(vis,0,sizeof(vis));while(!q.empty())q.pop();ans=0;tot=10;} int main() { scanf("%d",&t); while(t--) { init(); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=1;j<=m;j++) a[i][j]=s[j-1]-'0'; } for(int i=1;i<=k;i++)scanf("%d%d",&dx[i],&dy[i]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int sum=0; for(int o=1;o<=k;o++) { int tx=dx[o],ty=dy[o]; if(i+tx>=1&&i+tx<=n&&j+ty>=1&&j+ty<=m) sum+=a[i+tx][j+ty]; } q.push(mp(i,j,sum)); } while(!q.empty()&&tot) { tot--; email e=q.top();q.pop(); int px=e.x,py=e.y,now=e.v; for(int o=1;o<=k;o++) { int tx=dx[o],ty=dy[o]; if(px+tx>=1&&px+tx<=n&&py+ty>=1&&py+ty<=m) vis[px+tx][py+ty]=tot; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int sum=0; for(int o=1;o<=k;o++) { int tx=dx[o],ty=dy[o]; if(vis[i+tx][j+ty]==tot)continue; if(i+tx>=1&&i+tx<=n&&j+ty>=1&&j+ty<=m) sum+=a[i+tx][j+ty]; } ans=max(ans,sum+now); } } } printf("%d ",ans); } return 0; }