(vijos1037)搭建双塔

发表于 | 分类于 ，

一道经典神题

题目描述:

给出n(1<=n<=100)个水晶的高度, 用这些水晶搭建两座高度相同的塔, 求塔的最大高度(无解输出”Impossible”)

思路:

动规

用d(i,j)表示用前i个水晶, 两塔高度差为j时两塔中高塔的最大高度

转移方程见代码

答案为d(n,0)

当d(n,0)==0时输出Impossible

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Mn(105);
const int Mm(2005);
int d[Mn][Mm];
int a[Mn];
int main()
{
    int n;
    cin >> n;
    int sum(0); //最大高度差 
    for(int i(1);i<=n;++i)
        scanf("%d",a+i),sum+=a[i];
    memset(d,0xc0,sizeof d); //初始化为极小值 
    d[0][0] = 0;
    for(int i(1);i<=n;++i)
        for(int j(0);j<=sum;++j)
        {
            d[i][j] = d[i-1][j]; //不使用水晶 
            d[i][j] = max(d[i][j],d[i-1][j+a[i]]); //使用水晶搭在矮塔上, 矮塔还是矮塔 
            if(j>=a[i])	d[i][j] = max(d[i][j],d[i-1][j-a[i]]+a[i]); //使用水晶搭在高塔上 
            if(j<=a[i])	d[i][j] = max(d[i][j],d[i-1][a[i]-j]+j); //使用水晶搭在矮塔上, 矮塔变高塔 
        }
    if(d[n][0]==0)	cout << "Impossible"; //当最终建成高度为0时, 塔不存在 
    else			cout << d[n][0];
    return 0;
}