HDu 2830 Matrix Swapping II(dp)
We can swap any two columns any times, and we are to make the goodness of the matrix as large as possible.
3 4 1011 1001 0001 3 4 1010 1001 0001
4 2 Note: Huge Input, scanf() is recommended.
题意:一列一列的移动图,问最大的1组成的面积?
思路:每一行中,对高排序,高就是a【i】,长就是i,我代码中是j,然后就可以求最优解了
</pre><pre name="code" class="cpp">#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 1005 int h[N],a[N]; int n,m; int cmp(int a,int b) { return a>b; } int main() { int i,j; char c; while(~scanf("%d%d",&n,&m)) { getchar(); memset(h,0,sizeof(h)); int ans=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%c",&c); if(c=='1') h[j]++; else h[j]=0; } getchar(); for(j=1;j<=m;j++) a[j]=h[j]; sort(a+1,a+m+1,cmp); //强调一次,是一列一列的移动 for(j=1;j<=m;j++) ans=max(ans,a[j]*j); } printf("%d\n",ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。