DP 매일 3마리

오늘의 첫 번째 dp는 트리 모양의 그룹 or 라인 트리가 최적화된 최대 하위 라인과현장에서 Div2에서 사람됨을 가르쳤는데...그리고 현학현매로 롱롱을 터뜨리고 굵은 div2를 굴렸어요...고친 후에도 결말이 비교적 원만해요.첫 번째 DP 코드는 나의 허튼소리를 보았다. 그리고 두 번째 dp는 당황스럽게 이런 문제를 풀었다. 어떤 곳은 0이고 어떤 곳은 1이다. 가장 큰 정사각형 행렬을 구해서 안이 모두 1이 되도록 했다.그러면 f[i][j]를 설정하면 (i, j)를 오른쪽 하각의 정사각형의 최대 변장을 나타낸다. f[i][j]=min{f[i-1][j-1]+1,up[i][j],left[i][j]};up과left는 기점에서 이 방향으로 가면 최대 몇 개의 점을 통과할 수 있다는 것을 의미한다. 즉, 이 점을 오른쪽 아래 정점으로 하는 정사각형의 길이이다.코드:

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define Rep(i,n) for(int i = 1; i <= n ; i ++)
#define RepG(i,x) for(int i = head[x] ;~ i ; i = edge[i].next)
#define Rep_d(i,n) for(int i = n ; i > 0 ; i --)
#define Rep_0(i,n) for(int i = 0 ; i < n ; i ++)
#define RD(i,x,n) for(int i = x; i <= n ; i ++)
#define CLR(a,b) memset(a,b,sizeof(a))
#define v edge[i].to
using namespace std;
const int inf = 1 << 30; int read(){ char ch = getchar(); while(ch < '0' || ch > '9')ch = getchar ();
 int x = 0;
 while(ch >= '0' && ch <= '9')x = 10 * x + ch - '0',ch = getchar ();
 return x;
}
int f[1005][1005]; 
bool w[1005][1005];
int up[1005][1005],lft[1005][1005];
int main()
{
 int n = read(),m = read();
 Rep(i,n)
 Rep(j,m){
 w[i][j] = read();
 if(w[i][j])lft[i][j] = lft[i][j - 1] + 1;
 else lft[i][j] = 0;
 }
 Rep(i,m)
 Rep(j,n){
 if(w[j][i])up[j][i] = up[j - 1][i] + 1;
 else up[j][i] = 0;
 }
/*  Rep(i,n)
 Rep(j,m)
 printf("(%d,%d) %d %d
",i,j,up[i][j],lft[i][j]);*/
 CLR(f,127);
 f[1][1] = w[1][1];
 int ans = 0;
 Rep(i,n)
 Rep(j,m){
 if(w[i][j]){
 f[i][j] = min(f[i - 1][j - 1] + 1,min(up[i][j],lft[i][j]));
 ans = max(ans,f[i][j]);
 }
 else f[i][j] = 0;
 }
 printf("%d
",ans);
 return 0;
}

그래서 세 번째 문제는 물문제를 풀기로 했다. 서열 A = "a1 to an", 정의 d (A) = (http://pic002.cnblogs.com/images/2012/305173/2012062923105331.png); d (A) 구하기;즉, 최대 2개의 연속 필드 및

#include <cstdio>
#include <algorithm>
#include <cstring>
#define CLR(a,b) memset(a,b,sizeof(a))
#define Rep(i,n) for(int i = 1 ; i <= n ; i ++)
#define RepG(i,x) for(int i = head[x]; ~ i ; i = edge[i].next)
#define Rep_0(i,n) for(int i = 0 ; i < n ; i ++)
#define Rep_d(i,n) for(int i = n; i >= 1; i --)
#define u t[x] 
#define o t[y]
#define lc ch[0]
#define rc ch[1]
#define lson u.lc,l,mid
#define rson u.rc,mid + 1,r
#define N 50005
int l[N],r[N],a[N],n,lMax[N],rMax[N];
int main (){
    int cases;
    scanf("%d",&cases);
    while(cases --){
        CLR(lMax,-127),CLR(rMax,-127);
        scanf("%d",&n);
        Rep(i,n)
            scanf("%d",&a[i]);
        Rep(i,n)
            l[i] = std :: max(l[i - 1] + a[i],a[i]);
        Rep_d(i,n)
            r[i] = std :: max(r[i + 1] + a[i],a[i]);
        Rep(i,n)
            lMax[i] = std :: max(lMax[i - 1],l[i]);
        Rep_d(i,n)
            rMax[i] = std :: max(rMax[i + 1],r[i]);
        int Maxn = - (1 << 30);
        Rep(i,n)
            Maxn = std :: max(Maxn,lMax[i] + rMax[i + 1]);
        printf("%d
",Maxn);
    }
    return 0;

}

대개 x를 경계점으로 하는 좌우 양쪽에서 얻을 수 있는 최대치를 계산해 낸다.