[ An Ac a Day ^_^ ] hdu 2830 矩阵交换II

第一眼觉得是个dp 但是有了可以随意交换的条件觉得简单了不少

但是还是没做出来……

看了一下别人的做法才觉得自愧不如

因为所有列都可以随意交换 应该尽量把长的放在一起

那么将所有的矩形排序之后

以第j个矩形作为端点的大矩形面积是num[j]*j

只要从头开始都计算一遍就行了……

差距好大-_-||

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<ctime>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<cassert>
#include<sstream>
#include<stack>
#include<list>
#include<bitset>
#define cl(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr<<#x<<"=="<<(x)<<endl
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii; const int inf=0x3f3f3f3f;
const int maxn=1e9+;
const int mod=1e7+;
const double eps=1e-;
const double pi=acos(-); int dx[]= {,,,-,,-,,-};
int dy[]= {,-,,,-,,,-}; //---------------------------------------ヽ(^。^)丿 bool cmp(int a,int b)
{
return a>b;
} int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int ans=,num[],vis[];
char str[];
cl(vis,),cl(num,);
for(int i=;i<n;i++)
{
scanf("%s",str);
for(int j=;j<m;j++)
{
int ok=str[j]-'';
if(ok) vis[j]++;
else vis[j]=;
num[j]=vis[j];
}
sort(num,num+m,cmp);
for(int j=;j<m;j++)
ans=max(ans,num[j]*(j+));
}
printf("%d\n",ans);
}
return ;
}
/* 3 4
1011
1001
0001
3 4
1010
1001
0001 */
上一篇:jquery 中获取所有选中的checkbox的用法


下一篇:(转载)RHEL7(RedHat 7)本地源的配置