3 4 1011 1001 0001 3 4 1010 1001 0001
4 2 Note: Huge Input, scanf() is recommended.
#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);
}
}版权声明:本文为博主原创文章,未经博主允许不得转载。
HDU 2830 Matrix Swapping II (预处理的线性dp)
原文:http://blog.csdn.net/tc_to_top/article/details/46869537