[vijos1037] 쌍탑 세우기

제목 ←
제한과 답안, 도대체 어느 것이 수조 아래에 표시되어야 하는가
f[i][j]를 설정하여 i번째 수정을 얻기 위해 높이가 j일 때의 비교적 높은 탑의 가장 높은 높이에 대한 답안의 업데이트를 설정하고 네모난 것과 놓지 않는 것을 토론한다. dp[i][j]=dp[i-1][j];2. 놓으면 답안에 영향을 미치는 세 가지 상황이 있다. 1. 높은 탑에 놓으면 dp[i][j]=dp[i][j-h[i]]+h[i];//고도차 증가 h[i], 고탑 높이 증가 h[i]2, 낮은 탑 위에 놓고 높이는 원래의 고탑을 초과, dp[i][j]=dp[i-1][h[i]-j]+j;새로운 고도차는 고탑의 높이를 증가시킨다.3. 낮은 탑 위에 놓고 높이는 원래의 높은 탑을 초과하지 않는다. dp[i][j]=dp[i-1][j-h[i]];//고도차는 원래보다 h[i] 감소하고 고탑의 높이는 변하지 않는다
세 가지 상황은 모두 dp[i-1]에서 대응하는 상황이 합법적일 때 진행해야 한다는 것을 주의한다.
코드가 좀 어지러워요. 처음에는 상황을 고려하지 않았는데 2, 3이 양심적이어서 3이 지나갈 수 없어요. 그래서 1은 상태, 2, 3은 상태를 줘요.

#include
#include
#include
#include
using namespace std;
const int MAXN = 200 + 50;
int dp[MAXN][2050];
int h[MAXN],n;
int main(){
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++){
        scanf("%d",&h[i]);
    }
    int sum = 0;
    for(int i = 1;i <= n;i ++){
        sum += h[i];
        for(int j = 0;j <= sum;j ++){
            dp[i][j] = max(dp[i][j],dp[i - 1][j]);
            if(h[i] - j >= 0)
                if(dp[i - 1][h[i] - j] != -1){
                    dp[i][j] = max(dp[i][j],dp[i - 1][h[i] - j] + j);
                }
            if(dp[i][j] != -1){
                dp[i + 1][j + h[i + 1]] = max(dp[i + 1][j + h[i + 1]],dp[i][j] + h[i + 1]);
                if(j >= h[i + 1]){
                    dp[i + 1][j - h[i + 1]] = max(dp[i + 1][j - h[i + 1]],
                        dp[i][j]);
                }
            }
        }
    }
    if(dp[n][0] > 0)printf("%d",dp[n][0]);
    else printf("Impossible");
    return 0;
}