题解 P2423 【双塔】

经典做法见楼下。。

然而这里有一种简单粗暴的办法。

首先可以观察到，

如果左塔高度为i，右塔高度为j存在的话

则左塔高度为i+h1，右塔高度为j的情况存在

同理i，j+h1存在。（h1为某块水晶高度）。

根据这个性质，我们其实没必要按最大值dp，而是按存在性dp

最后扫一遍最大的可能情况，得出结果。

然后需要注意两点，第一点是不重不漏的的枚举所有的积木。

第二就是，在遍历二维数组时需要倒着扫，因为如果我们从前往后更新的话，就会多次使用同一水晶，

导致错误。

具体见代码。

#include<stdio.h>
using namespace std;
int n;bool d[2000][2000];
int h[100];int sum;int cont;
int res=0;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&h[i]);
        sum+=h[i];//计算可能的最高值，即总高度的一半
    }
    d[0][0]=true;cont=sum/2;//边界条件，显然不放水晶的情况一定存在
    for(int i=0;i<n;i++)//每放一块积木就要遍历整个二维数组，复杂度为（n*cont*cont）
    {
        for(int j=cont;j>=0;j--)//从总高一半倒着扫
        {
            for(int k=cont;k>=0;k--)//双层循环遍历整个二位数组
            {
                if(d[j][k]==true)
                {
                    d[j+h[i]][k]=true;d[j][k+h[i]]=true;//转移
                }
            }
        }
    }
    for(int i=0;i<=cont;i++)//扫一遍最大值
    {
        if(d[i][i])res=i;
    }
    if(res==0)printf("Impossible");//如果只有零就输出impossible
    else printf("%d",res);
    return 0;//拜拜程序~
}