P1284 三角形牧场
Portal.
首先，我们需要一些初中数学知识——秦九韶公式（又名海伦公式）：
p = a + b + c 2 S = p ( p − a ) ( p − b ) ( p − c ) \begin{align} &p=\dfrac{a+b+c}{2}\\ &S=\sqrt{p(p-a)(p-b)(p-c)} \end{align} p=2a+b+cS=p(p−a)(p−b)(p−c)
假设 f ( k , i , j ) f(k,i,j) f(k,i,j) 表示前 k k k 个木板能否围成两边长为 i i i、 j j j 的三角形，状态转移时有三种情况：
- 把第 k k k 个木板加到边 i i i 中，前 k − 1 k-1 k−1 个木板要围成两边长为 i − l k i-l_k i−lk、 j j j 的三角形，即 f ( k − 1 , i − l k , j ) f(k-1,i-l_k,j) f(k−1,i−lk,j)。
- 把第 k k k 个木板加到边 j j j 中，同理 f ( k − 1 , i , j − l k ) f(k-1,i,j-l_k) f(k−1,i,j−lk)。
- 把第 k k k 个木板加到第三条边中， f ( k − 1 , i , j ) f(k-1,i,j) f(k−1,i,j)。
三者或运算之后的真假即结果。
可以观察到，转移过程中只跟前 k − 1 k-1 k−1 个木板的状态有关，所以我们可以采用背包的滚动数组思想，压掉 k − 1 k-1 k−1 这一层。
注意：
- 要用
double。 - 要反着枚举 i i i、 j j j，这要参考 01 01 01 背包的思想，如果正着枚举会重复使用某一条边，并且压掉的 k − 1 k-1 k−1 这一层循环不能保存之前的状态会被替代。
- 初始化： f ( 0 , 0 ) = 1 f(0,0)=1 f(0,0)=1。
代码如下：
#include <bits/stdc++.h>
using namespace std;int l[45];
bool f[805][805];
double ans;double work(double a,double b,double c)
{double p=(a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));
}bool check(int a,int b,int c)
{if(a+b>c&&a+c>b&&b+c>a) return 1;return 0;
}int main()
{int n,cc,i,j,k;cin>>n;for(i=1;i<=n;i++) cin>>l[i],cc+=l[i];f[0][0]=1;for(k=1;k<=n;k++)for(i=cc/2;i>=0;i--)for(j=cc/2;j>=0;j--){if(i-l[k]>=0&&f[i-l[k]][j]) f[i][j]=1;else if(j-l[k]>=0&&f[i][j-l[k]]) f[i][j]=1;}ans=-1;for(i=cc/2;i>0;i--)for(j=cc/2;j>0;j--){if(!f[i][j]) continue;if(!check(i,j,cc-i-j)) continue;ans=max(ans,work(i,j,cc-i-j));}if(ans!=-1) cout<<(long long)(ans*100);else cout<<-1;return 0;
}