Vijos P1037 듀얼 타워 구축(동적 계획)

분석: dp[i][j]는 앞의 I개 숫자의 고도 차이가 J인 고탑의 높이를 나타낸다. 그래서 YY는 전이 방정식을 낸다.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n;
int dp[105][20005];
int num[105];
int main()
{
    scanf("%d",&n);
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        sum+=num[i];
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    int a;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=sum;j++)
        {
            if(dp[i-1][j]>-1)
                dp[i][j]=dp[i-1][j];
            if(num[i]>j&&dp[i-1][num[i]-j]>-1)
                dp[i][j]=max(dp[i][j],dp[i-1][num[i]-j]+j);
            if(j+num[i]<=sum&&dp[i-1][j+num[i]]>-1)
                dp[i][j]=max(dp[i][j],dp[i-1][j+num[i]]);
            if(j>=num[i]&&dp[i-1][j-num[i]]>-1)
                dp[i][j]=max(dp[i][j],dp[i-1][j-num[i]]+num[i]);
        }
    }
    if(dp[n][0]>0)
        printf("%d
",dp[n][0]);
    else printf("Impossible
");
    return 0;
}