题解 P2423 【双塔】

经典做法见楼下。。 然而这里有一种简单粗暴的办法。 首先可以观察到， 如果左塔高度为i，右塔高度为j存在的话 则左塔高度为i+h1，右塔高度为j的情况存在 同理i，j+h1存在。（h1为某块水晶高度）。 根据这个性质，我们其实没必要按最大值dp，而是按存在性dp 最后扫一遍最大的可能情况，得出结果。 然后需要注意两点，第一点是不重不漏的的枚举所有的积木。 第二就是，在遍历二维数组时需要倒着扫，因为如果我们从前往后更新的话，就会多次使用同一水晶， 导致错误。 具体见代码。 ```cpp #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;//拜拜程序~ } ```