BZOJ 1057 ZJOI 2007 바둑판 제작 DP+ 현수법
사고방식: 사실 모든 (i+j) & 1의 위치에서 숫자가 틀리거나 틀리면 0 또는 1의 최대 정사각형과 직사각형으로 변한다.첫 번째 질문은 물DP이고, 두 번째 질문은 단조로운 창고나 현수막으로 할 수 있다.다 잘 써요.
CODE:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 2010
using namespace std;
int m,n;
int src[MAX][MAX];
int f[MAX][MAX];
int up[MAX][MAX],_left[MAX][MAX],_right[MAX][MAX];
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j) {
scanf("%d",&src[i][j]);
if((i + j)&1)
src[i][j] ^= 1;
}
int ans = 0;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(src[i][j]) {
f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1;
ans = max(ans,f[i][j]);
}
memset(f,0,sizeof(f));
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(!src[i][j]) {
f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1;
ans = max(ans,f[i][j]);
}
cout << ans * ans << endl;
ans = 0;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j)
_left[i][j] = src[i][j] ? _left[i][j - 1] + 1:0;
for(int j = n; j; --j)
_right[i][j] = src[i][j] ? _right[i][j + 1] + 1:0;
}
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(src[i][j] && src[i - 1][j]) {
up[i][j] = up[i - 1][j] + 1;
_left[i][j] = min(_left[i][j],_left[i - 1][j]);
_right[i][j] = min(_right[i][j],_right[i - 1][j]);
ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1));
}
memset(_left,0,sizeof(_left));
memset(_right,0,sizeof(_right));
memset(up,0,sizeof(up));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j)
_left[i][j] = src[i][j] ? 0:_left[i][j - 1] + 1;
for(int j = n; j; --j)
_right[i][j] = src[i][j] ? 0:_right[i][j + 1] + 1;
}
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(!src[i][j] && !src[i - 1][j]) {
up[i][j] = up[i - 1][j] + 1;
_left[i][j] = min(_left[i][j],_left[i - 1][j]);
_right[i][j] = min(_right[i][j],_right[i - 1][j]);
ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1));
}
cout << ans << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.