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

更好的阅读体验戳此进入

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

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

题面

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

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

Vijos-1037 搭建双塔

JDOJ-1222: VIJOS-P1037 搭建双塔

输入格式

$n$$n$

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

Examples

Input_1

xxxxxxxxxx
2
1
5
2
1 3 4 5 2

Output_1

xxxxxxxxxx
1
1
7

Solution

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

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

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

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

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

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

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

Code

xxxxxxxxxx
70
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17
using namespace __gnu_pbds;
18

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

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

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

31
#define MINF -0x3f3f3f3f
32
int N;
33
int h[110];
34
int dp[110][2100];
35

36
int main(){
37
    dp[0][0] = 0;
38
    for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
39
    N = read();
40
    int sum(0);
41
    for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
42
    for(int i = 1; i <= N; ++i){
43
        for(int j = 0; j <= sum; ++j){
44
            dp[i][j] = dp[i - 1][j];
45
            if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
46
            else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
47
            if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
48
        }
49
    }
50
    if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
51
    else printf("Impossible\n");
52
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
53
    return 0;
54
}
55

56
template<typename T>
57
inline T read(void){
58
    T ret(0);
59
    short flag(1);
60
    char c = getchar();
61
    while(c != '-' && !isdigit(c))c = getchar();
62
    if(c == '-')flag = -1, c = getchar();
63
    while(isdigit(c)){
64
        ret *= 10;
65
        ret += int(c - '0');
66
        c = getchar();
67
    }
68
    ret *= flag;
69
    return ret;
70
}

Code - C++98(JDOJ)

xxxxxxxxxx
68
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17
using namespace __gnu_pbds;
18

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

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

28
template<typename T>
29
inline T read(void){
30
    T ret(0);
31
    short flag(1);
32
    char c = getchar();
33
    while(c != '-' && !isdigit(c))c = getchar();
34
    if(c == '-')flag = -1, c = getchar();
35
    while(isdigit(c)){
36
        ret *= 10;
37
        ret += int(c - '0');
38
        c = getchar();
39
    }
40
    ret *= flag;
41
    return ret;
42
}
43

44
#define read read < int >
45
#define MINF -0x3f3f3f3f
46
int N;
47
int h[110];
48
int dp[110][2100];
49

50
int main(){
51
    dp[0][0] = 0;
52
    for(int i = 1; i <= 2010; ++i)dp[0][i] = MINF;
53
    N = read();
54
    int sum(0);
55
    for(int i = 1; i <= N; ++i)h[i] = read(), sum += h[i];
56
    for(int i = 1; i <= N; ++i){
57
        for(int j = 0; j <= sum; ++j){
58
            dp[i][j] = dp[i - 1][j];
59
            if(j >= h[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]);
60
            else dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j);
61
            if(j + h[i] <= sum)dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]);
62
        }
63
    }
64
    if(dp[N][0] > 0)printf("%d\n", dp[N][0]);
65
    else printf("Impossible\n");
66
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67
    return 0;
68
}

UPD

update-2022_09_27 初稿