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

时间：2021-02-09 13:09:35

第一眼觉得是个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

 */

相关文章