lightoj 1126 - Building Twin Towers（dp，递推）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1126

题解：一道基础的dp就是简单的递推可以设dp[height_left][height_right]，但是这样显然回boom内存，所以不妨直接考虑两座塔之间的差于是便有了dp[i][j]表示考虑到第几个时两座塔差值是多少，然后就是递推了，要么加积木嫁到高的塔上要么就嫁到底的塔上要么都不嫁，这样递推方程就好写了。如果这样还是boom内存的话可以考虑用滚动优化i这一维。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 5e5 + ;

int a[] , dp[][M];

int main() {

    int t;

    scanf("%d" , &t);

    int Case = ;

    while(t--) {

        int n;

        scanf("%d" , &n);

        int sum = ;

        for(int i =  ; i <= n ; i++) {

            scanf("%d" , &a[i]);

            sum += a[i];

        }

        sum /= ;

        memset(dp , - , sizeof(dp));

        dp[][] = ;

        int flag = ;

        for(int i =  ; i <= n ; i++) {

            flag = i % ;

            for(int j =  ; j <= sum ; j++) {

                dp[flag][j] = max(dp[flag ^ ][j] , dp[flag][j]);

                if(dp[flag ^ ][j] != -) {

                    dp[flag][j + a[i]] = max(dp[flag][j + a[i]] , dp[flag ^ ][j] + a[i]);

                    if(j >= a[i]) {

                        dp[flag][j - a[i]] = max(dp[flag][j - a[i]] , dp[flag ^ ][j]);

                    }

                    else {

                        dp[flag][a[i] - j] = max(dp[flag][a[i] - j] , dp[flag ^ ][j] - j + a[i]);

                    }

                }

            }

        }

        if(dp[flag][] > ) {

            printf("Case %d: %d\n" , ++Case , dp[flag][]);

        }

        else {

            printf("Case %d: impossible\n" , ++Case);

        }

    }

    return ;

}

巴特西

lightoj 1126 - Building Twin Towers（dp，递推）

最新文章

热门文章