단순 DP 요약

1 hdu 1003
최대 연속 하위 세그먼트 및
i) 시작 및 끝 좌표 상황 기록
dp[i] 이전 i 개수 중 a[i]를 끝으로 하는 최대 연속 자단과
dp[n] = max{ dp[i-1] + a[i] , a[i] }
ii) 최대 필드와

        scanf("%d",&n); scanf("%d",&a);  ans=t=a;
        for(i=1;i

무료 파이
dp[i][x]i초 동안 위치 x, 전 i초 동안 가장 많이 받은 파이
 dp[i][j] = max(dp[i-1][j] , max(dp[i-1][j+1] , dp[i-1][j-1])) + a[i][j] ;
초기화 주의: dp[0[시작 위치] = 0;dp[0[기타 위치] = 마이너스 무궁화
3 hdu 1087 super jumping
dp[i]가 a[i]로 끝나는 최대 및
dp[i] = max{dp[j] , j < i && a[j] < a[i] } + a[i]
4 hdu1159 최장 공통 서열
L[i][j] = L[i-1][j-1] + 1  , a[i] = b[j] ;
L[i][j] = max(L[i][j-1] , L[i-1][j])  a[i] != b[j] ;
원숭이와 바나나
컨디션 표시

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 205 ;
int dp[maxn] ;
struct block
{
    int l , w , h ;
}B[maxn];

bool cmp (block A , block B)
{
    if(A.l < B.l) return true ;
    else if(A.l == B.l && A.w < B.w ) return true ;
    else return false ;
}

int main()
{
    //freopen("a.txt" ,"r" , stdin) ;
    int n , x , y , z , Case = 1 , Len ;
    int MaxHeight , MaxJ ;
    while(scanf("%d" , &n) != EOF && n)
    {
        Len = 0 ;
        while(n --)
        {
            scanf("%d%d%d" , &x , &y , &z) ;
            B[Len].l = x , B[Len].w = y , B[Len].h = z , Len ++ ;
            B[Len].l = x , B[Len].w = z , B[Len].h = y , Len ++ ;
            B[Len].l = y , B[Len].w = x , B[Len].h = z , Len ++ ;
            B[Len].l = y , B[Len].w = z , B[Len].h = x , Len ++ ;
            B[Len].l = z , B[Len].w = x , B[Len].h = y , Len ++ ;
            B[Len].l = z , B[Len].w = y , B[Len].h = x , Len ++ ;
        }
        sort(B , B + Len , cmp) ;
        dp[0] = B[0].h ;
        MaxHeight = dp[0] , MaxJ = 0 ;
        for(int i = 1 ; i < Len ; i ++)
        {
            dp[i] = 0 ;
            for(int j = 1 ; j < i ; j ++)
            {
                if(B[j].l < B[i].l && B[j].w < B[i].w)
                    dp[i] = max(dp[i] , dp[j]) ;
            }
            dp[i] += B[i].h ;
            if(dp[i] > MaxHeight)  { MaxHeight = dp[i]  ; MaxJ = i ; }

        }
        printf("Case %d: maximum height = %d 
" , Case ++ , MaxHeight ) ;
    }
    return 0;
}

동적 기획 총결산: 1 상태의 표시 2 현재 상태가 어떤 상태(이미 알고 있는/앞)의 상태로 바뀔 수 있는지를 고려하여 현재 상태의 최선의 선택을 찾아낸다.