ZOJ Problem Set - 2297 Survival [상압 dp]

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long N = 22;
const int inf = 0x3f3f3f3f;
int dp[1<<N];
pair<int,int> p[N];
int main()
{
    int n,boss;
    while(~scanf("%d",&n) && n)
    {
        n--;
        for(int i=0;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            p[i]=make_pair(x,y);
        }
        scanf("%d",&boss);
        memset(dp,0,sizeof(dp));
        int ans = 0;
        dp[0]=100;
        for(int st=1;st<(1<<n);st++)
        {
            dp[st]=-inf;  //        
            for(int j=0;j<n;j++)
                if(st&(1<<j)&&dp[st&~(1<<j)]>=p[j].first)
                {
                    dp[st]=max(dp[st],dp[st&~(1<<j)]-p[j].first+p[j].second);
                    if(dp[st]>100)
                        dp[st]=100;
                }
        }
        if(dp[(1<<n)-1]>=boss)
            puts("clear!!!");
        else
            puts("try again");
    }
    return 0;
}