题意：给一个n*m的矩阵，这个矩阵中的第i行j列有一个欢乐值和这个位置的人的性别，如果欢乐值为负数的话就不能选这个人。
求：选择一个子矩阵，这个子矩阵中不能包含欢乐值为负数，并且这个矩阵中男孩的个数大于等于b，这个矩阵中女孩的个数大于等于g (n,m,b,g都将给出)
(n <= 100,m <= 2000)
我的做法：
nnm的复杂度
我一开始是这么想的。
输入这个矩阵之后，预处理行的欢乐值，男孩的个数，女孩的个数，再预处理左上角到该点一共有多少欢乐值。男孩的个数。女孩的个数。然后求出所有欢乐值为负数的点。然后按列排序。最后枚举行，对列的开始点和终点进行判断。这样做的结果是TLE了。。
后来观察大牛的代码发现我还是太天真了。大牛的代码是预处理列。因为要枚举行。所以只需要预处理列就可以了。。
因为我的预处理是行预处理的，但是我又枚举行。这样的话计算起来不是很方便。。
还是太天真了，不多说。上代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 110
#define MAXM 2010
typedef long long LL;
int n,m,b,g;
int sgi[MAXN][MAXM];
int sbi[MAXN][MAXM];
LL svi[MAXN][MAXM];
int st[MAXN][MAXM];
int sv[MAXN][MAXM];
int last[MAXN][MAXM];
int main()
{
memset(sgi,0,sizeof(sgi));
memset(sbi,0,sizeof(sbi));
memset(svi,0,sizeof(svi));
memset(last,0,sizeof(last));
while(~scanf("%d%d%d%d",&n,&m,&b,&g)){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d%d",&sv[i][j],&st[i][j]);
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++){
sbi[i][j]=sbi[i-1][j]+(st[i][j]==1);
sgi[i][j]=sgi[i-1][j]+(st[i][j]==2);
svi[i][j]=svi[i-1][j]+sv[i][j];
last[i][j]=last[i-1][j];
if(sv[i][j]<0)last[i][j]=i;
}
LL ans=-1;
for(int x=1;x<=n;x++){
for(int x1=x;x1<=n;x1++){
LL nv,nb,ng,lv,lb,lg;
nv=nb=ng=lv=lb=lg=0;
for(int i=1;i<=m;i++){
nv+=svi[x1][i]-svi[x-1][i];
nb+=sbi[x1][i]-sbi[x-1][i];
ng+=sgi[x1][i]-sgi[x-1][i];
if(last[x1][i]>=x){
lv=nv;
lb=nb;
lg=ng;
continue;
}
if(nb-lb>=b&&ng-lg>=g){
ans=max(ans,nv-lv);
}
}
}
}
if(ans==-1)puts("No solution!");
else printf("%lld\n",ans);
}
return 0;
}
|
