HDU 4314 드워프 탈출 dp

제목: 깊이가 h인 우물에 n개의 드워프가 갇혀 있으며, 드워프마다ai(발에서 어깨 높이)와bi(팔 길이)가 존재하며, a1+a2+...+ak-1+ak+bk>=h, 드워프k는 우물에서 탈출할 수 있습니다.최대 몇 명은 탈출할 수 있느냐고 물었다.
문제풀이: dp[i][j]는 전 i인 중 j인을 탈출한 후에 남은 우물에서 드워프가 탈출하려면 최소한 한 사람이 필요로 하는 최소 높이가 얼마나 되는지를 의미한다. 분석한 결과 다음과 같다. 탈출한 j인 중 마지막에 탈출한 사람은 반드시ai+bi가 가장 크다. 이렇게 해야만 dp치가 가장 좋은 것을 얻을 수 있다. 먼저 드워프에게ai+bi가 크고 작은 순서에 따라 현재 i인이 탈출할 수 있는지 고려해야 한다.즉 dp[i][j]는 두 가지 상황에서만 얻을 수 있다.
dp[i-1][j]:i 위치의 사람이 탈출하지 않았기 때문에 필요한 높이는 dp[i-1][j]-a[i]이다.
dp[i-1][j-1]: i 위치의 사람이 탈출했습니다. 필요한 높이는 두 가지가 있습니다.
1i의 키와 팔의 길이가 충분하여 이전에 필요한 높이를 이용하여 탈출할 수 있다. 이때 필요한 높이는 dp[i-1][j-1]이다.
2i의 키와 팔의 길이가 크지 않다. 이때 i가 가장 먼저 탈출하기 때문에 필요한 높이는 전 i-1명이 i의 탈출을 도와주고 필요한 높이는 H-sumA[i]-b[i]이다.
상기 두 가지 상황은 모두 만족해야 dp[i][j]를 얻을 수 있기 때문에 최대치를 취해야 한다. 종합적으로 dp방정식을 얻어야 한다. dp[i][j]=MIN(dp[i-1][j]-dwarf[i].a,MAX(dp[i-1][j-1],h-sum[i]-dwarf[i].b)).Sure 오리지널, 전재는 출처를 밝혀 주십시오.

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int inf = 1 << 29;
const int maxn = 2002;
struct D
{
    int a,b;
    bool operator < (const D &other) const
    {
        return a + b > other.a + other.b;
    }
}dwarf[maxn];
int sum[maxn],dp[maxn][maxn];
int n,h;

void read()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&dwarf[i].a,&dwarf[i].b);
    }
    scanf("%d",&h);
    sort(dwarf + 1 , dwarf + n + 1);
    sum[0] = 0;
    for(int i=1;i<=n;i++)
    {
        sum[i] = sum[i-1] + dwarf[i].a;
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            dp[i][j] = inf;
        }
    }
    return;
}

void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j] = MIN(dp[i-1][j] - dwarf[i].a , MAX(dp[i-1][j-1] , h - sum[i] - dwarf[i].b));
        }
    }
    for(int i=n;i>=0;i--)
    {
        if(dp[n][i] <= 0)
        {
            printf("%d
",i);
            break;
        }
    }
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        read();
        solve();
    }
    return 0;
}