[luogu] P1284 三角形牧场 背包问题

前言

感觉是背包,但是又感觉不是背包 传送门 :

思路

前置知识

• 知道三边可以求面积的是海伦公式
• 我们可以在知道两边的情况下,第三边可以用 s u m − x 1 − x 2 sum-x1-x2 sum−x1−x2 表示出来

因此我们状态表示 : f [ k ] [ i ] [ j ] f[k][i][j] f[k][i][j] 是否可以用前 k k k 个木板构成边分别是 i , j i,j i,j的三角形

特别的 : 我们可以构造出 0 , 0 0,0 0,0的三角形 (我也不知道为什么

状态转移 : 对于当前第 k k k个木板

• 如果放在,第 i i i条, f [ k − 1 ] [ i − a [ k ] ] [ j ] f[k-1][i-a[k]][j] f[k−1][i−a[k]][j]
• 如果放在,第 j j j条, f [ k − 1 ] [ i ] [ j − a [ k ] ] f[k-1][i][j-a[k]] f[k−1][i][j−a[k]]
• 放在第三条上 f [ k − 1 ] [ i ] [ j ] f[k-1][i][j] f[k−1][i][j]

显然 : f [ k − 1 ] f[k-1] f[k−1]这一层循环是可以直接去掉的,所以我们就优化成了两层

CODE

const int N = 50 , M = 810;
int a[N],n;
int f[M][M];
int sum ; 
double ans;
bool check(int x,int y,int z)
{
	if(x+y>z && x+z>y && y+z>x)return true;
	return false;
}

double cal(double x,double y,double z)
{
	double p = (x+y+z)/2;
	return sqrt(p*(p-x)*(p-y)*(p-z));
}
void solve()
{	
	cin>>n;
	f[0][0] = 1;
	
	for(int i=1;i>a[i];
		sum+=a[i];
	}
	
	for(int k=1;k=0;i --)
			for(int j = sum/2;j>=0;j--)
			{
				if(i-a[k]>=0 && f[i-a[k]][j]) f[i][j] = 1;
				if(j-a[k]>=0 && f[i][j-a[k]]) f[i][j] = 1;
			}
	}
	
	for(int i=sum/2;i;i--)
		for(int j =sum/2;j;j--)
		{
			if(!f[i][j])
			continue;
			if(!check(i,j,sum-i-j))
			continue;
			ans =  max(ans,cal(i,j,sum-i-j));
		}
		
	if(!ans)
	cout