[vijos1037]搭建双塔

发布于 2017-09-13  136 次阅读



题目(vijos)
来说说这题吧。
首先,这肯定是一道dp题,那么就要先把状态定义好,以便转移。
用dp[i][j]表示第一座塔高度为i,第二座塔高度为j?
显然不好转移,因为只有当i==j时才有效。
而这道题和高度差有关:只有两座塔高度差为0时才算搭建成功。
那就这样定义:
dp[i][j]表示选到第i块水晶,两座塔的高度差为j时,低塔的最大高度。
这就很好转移了:转移分四种情况,
1.不选当前水晶
dp[i][j]=dp[i-1][j];
2.选择当前水晶,并将其放在高塔上
dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]);   //a[i]表示第i块水晶的高度
因为放在高塔上不影响低塔的高度,但高度差会增加a[i]。
3.选择当前水晶,并将其放在低塔上,但低塔不会变成高塔
dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+a[i]);
既然不影响低塔与高塔的关系(即低塔还是原来那座塔,高塔还是原来那座塔),
那么高度差就会减小a[i],低塔的最大高度会增加a[i]。
4.选择当前水晶,并将其放在低塔上,且低塔变高塔,高塔变低塔
dp[i][j]=max(dp[i][j],dp[i-1][a[i]-j]+a[i]-j);
这个用数学关系推一下吧:
设h1为原低塔高度,h2为原高塔高度,那么j=h2-h1,
然后h1加上a[i],原方程变成:j-a[i]=h2-(h1+a[i]),
由于此时低塔超过高塔高度,则j-a[i]为负数,所以此时高度差为-(j-a[i])=a[i]-j,
低塔变高塔,高塔变低塔,那么此时低塔高度最大值就是原高塔的高度。
完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,h;
int a[105];
int dp[105][2005];
int ans;
int main()
{
	memset(dp,-0x7f,sizeof dp);
	dp[0][0]=0;
	scanf(
	for (int i=1;i<=n;++i)
		scanf(
	for (int i=1;i<=n;++i)
	{
		for (int j=h;j>=0;--j)
		{
			dp[i][j]=dp[i-1][j];
			dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i]);
			if (j>=a[i])
			 dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]);
			else
			 dp[i][j]=max(dp[i][j],dp[i-1][a[i]-j]+a[i]-j);
		}
	}
	if (!dp[n][0]) puts("Impossible");
	else printf(
	return 0;
}