标签：return int 题解 ret getchar Vijos 1037 dp define

关于一个人类智慧的DP - Vijos 1037 搭建双塔

目录

• 关于一个人类智慧的DP - Vijos 1037 搭建双塔
  • 更好的阅读体验戳此进入
  • 题面
  • 输入格式
  • Examples
    • Solution
  • Code
  • Code - C++98(JDOJ)
  • UPD

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

做这道题的原因是在写 POI 的一道人类智慧题的时候有点想不明白，然后看题解里有人说中间有一步和这道题的思路差不多，于是决定先把这道题做一下。

题面

给你 $ n $ 块水晶，每块水晶有一个高度 $ h_i $，你可以任选其中一些块，向上叠在一起来搭建两座塔，使得两座塔的高度相同且不为 $ 0 $，能搭建的话输出最大高度，否则输出 Impossible。

$ 1 \le n \le 100, 0 \le \sum_{i = 1}^{n}h_i \le 2000 $。

Vijos-1037 搭建双塔

JDOJ-1222: VIJOS-P1037 搭建双塔

输入格式

$ n $

$ h_1 $ $ h_2 $ $ \cdots $ $ h_n $

Examples

Input_1

5
1 3 4 5 2

Output_1

7

Solution

第一次听说还有这种状态设计

令 $ dp(i, j) $ 表示考虑到第 $ i $ 块水晶，能搭建成差值为 $ j $ 的两座塔中较高塔的高度，这个东西似乎叫做差值 DP。

我们考虑转移，显然可以分成以下几种情况：

1. 舍弃这块水晶：$ dp(i - 1, j) $。
2. 将这块水晶放到较高的塔上：$ dp(i - 1, j - h_i) + h_i $。
3. 将这块水晶放到较低的塔山，且这样之后两座塔之间的大小关系不变：$ dp(i - 1, j + h_i) $。
4. 将这块水晶放到较低的塔山，且这样之后两座塔之间的大小关系改变：$ dp(i - 1, h_i - j) + j $。

关于第四个方程可以看下面这个图，不难发现有 $ j' = h_i - j $，那么 $ dp(i, j) = dp(i - 1, j') + j = dp(i - 1, h_i - j) + j $。

所以转移就是上面四个式子求最大值即可。

复杂度 $ O(n\sum h_i) $。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

/******************************
abbr

******************************/

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template<typename T = int>
inline T read(void);

#define MINF -0x3f3f3f3f
int N;
int h[110];
int dp[110][2100];

int main(){
    dp[0][0] = 0;
    for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
    N = read();
    int sum(0);
    for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j <= sum; ++j){
            dp[i][j] = dp[i - 1][j];
            if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
            else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
            if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
        }
    }
    if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
    else printf("Impossible\n");
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

Code - C++98(JDOJ)

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

/******************************
abbr

******************************/

using namespace std;
using namespace __gnu_pbds;

// mt19937 rnd(random_device{}());
// int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
// bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

#define read read < int >
#define MINF -0x3f3f3f3f
int N;
int h[110];
int dp[110][2100];

int main(){
    dp[0][0] = 0;
    for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
    N = read();
    int sum(0);
    for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j <= sum; ++j){
            dp[i][j] = dp[i - 1][j];
            if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
            else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
            if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
        }
    }
    if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
    else printf("Impossible\n");
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

UPD

update-2022_09_27 初稿

标签：return,int,题解,ret,getchar,Vijos,1037,dp,define
From： https://www.cnblogs.com/tsawke/p/16786785.html