2009 Multi-University Training Contest 2 – Host by TJU题目链接：?pid=2830题目大意：给一个0/1矩阵，可以任意交换其中的两列，求由1组成的最大子矩形的面积题目分析：预处理出每个点下方有多个连续的1即cnt[i][j]，，对每行的cnt值从大到小排序，枚举列dp即可，dp[i]表示以第i行为上边的矩形的面积最大值，转移方程：dp[i] = max(dp[i], j * cnt[i][j])#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 1e3 + 5;int const INF = 0x3fffffff;char s[MAX][MAX];int cnt[MAX][MAX];int dp[MAX];int n, m;bool cmp(int a, int b){return a > b;}int main(){while(scanf("%d %d", &n ,&m) != EOF){memset(cnt, 0, sizeof(cnt));memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++)scanf("%s", s[i] + 1);for(int i = n; i >= 1; i–)for(int j = 1; j <= m; j++)if(s[i][j] – '0')cnt[i][j] = cnt[i + 1][j] + 1;for(int i = 1; i <= n; i++){sort(cnt[i] + 1, cnt[i] + 1 + m, cmp);for(int j = 1; j <= m; j++)if(cnt[i][j])dp[i] = max(dp[i], j * cnt[i][j]);}int ans = 0;for(int i = 1; i <= n; i++)ans = max(ans, dp[i]);printf("%d\n", ans);}}
觉得自己做的到和不做的到，其实只在一念之间
