2014年广州区域赛i题解
题意
从给的n根木棍中选择一部分组成若干个三角形，问最大三角形总面积为多少。
笺释
样例2懵了半个小时才转过来弯，原来13是比12大的，在我的印象里13一直都比12小才对，为什么呢，可能是因为西方13是不吉利的数字所以太少出现了吧=。=
这道题能不能贪呢，我这边是证不出来的，而我的话如果证不出来贪心就不会用的。
但是有一点是确定的
先选出来3个组成一个最大的三角形，再组成第二大的三角形，这样总面积最大是没有保证的。
但是这给了我们提示
也是dp的惯例了，如果局部贪心保证不了，就索性记录所有情况，然后用之前的情况更新之后的就可以。
我的思路是这样的
先预处理出所有组成1个，2个，3个，4个(最多4个)三角形所用木棍的所有情况，用二进制集合的形式加以表示，具体是这样的:
void init()
{
//所有长度为3 6 9 12的子集
for(int i=1;i<=4;i++)
{
//k为长度
//i为三角形个数
int k=getq[i];
int comb=(1<<k)-1;
while(comb<(1<<12))
{
box[i][++sum[i]]=comb;
int x=comb& -comb,y=comb+x;
comb=((comb& ~y)/x>>1)|y;
}
}
}
这种表示办法在挑战程序设计竞赛上是有严格推导的，有兴趣的可以去看看呢。
然后就是状压dp的常规思路了，枚举所有状态情况，根据之前的状态更新之后的状态。
}
for(int i=(1<<3)-1;i<=(1<<n)-1;i++)
{
int num=cal(i);
if(!(num%3))
{
int k=num/3;
for(int j=1;j<=sum[k-1];j++)
{
int r=box[k-1][j];
if((r&i)==r)//这里是判断用来更新状态i的状态r是i的子集
{
if(okc(i^r))//这里是用取补集的办法得到新状态所增加的三角形
{
dp[i]=max(dp[i],dp[r]+counts(i^r));
ans=max(ans,dp[i]);
}
}
}
}
}
为什么不用搜索呢
这个题数据范围其实很像是dfs的范围，但是至少对于我来说dfs这个角度不太好想，因为这个题多多少少是可以用dp的递推结构的，尽管最多也就是推四步而已，当然我并不是在说递推是dp的专利，实际上用dfs应该也是可以写的，不过最终思想应该都是一个递推思想，我想说的是，实际上dfs和dp之间并没有一道很明显的分界线，很多时候是可以混用的，很多时候dfs不太熟悉或者不太好想转化成dp是很好的。
我说话可真绕。=。=
完整代码
#include<bits/stdc++.h>
using namespace std;
int n;
int sum[4];
int box[5][1<<13];
int a[15];
int getq[5]={0,3,6,9,12};
double dp[1<<13];
double getnum(int a1,int a2,int a3)
{
double p=(a1+a2+a3)*1.0/2;
return sqrt(p*(p-a1*1.0)*(p-a2*1.0)*(p-a3*1.0));
}
bool ok(int a1,int a2,int a3)
{
//两边之和大于第三边
if(a1+a2<a3)
{
return false;
}
if(a1+a3<a2)
{
return false;
}
if(a3+a2<a1)
{
return false;
}
return true;
}
void init()
{
//所有长度为3 6 9 12的子集
for(int i=1;i<=4;i++)
{
//k为长度
//i为三角形个数
int k=getq[i];
int comb=(1<<k)-1;
while(comb<(1<<12))
{
box[i][++sum[i]]=comb;
int x=comb& -comb,y=comb+x;
comb=((comb& ~y)/x>>1)|y;
}
}
}
int cal(int x)
{
int ret=0;
for(int i=1;i<=n;i++)
{
if(x>>(i-1)&1)
{
ret++;
}
}
return ret;
}
bool okc(int x)
{
int ret[4],p=1;
for(int i=1;i<=n;i++)
{
if(x>>(i-1)&1)
{
ret[p++]=i;
}
}
if(ok(a[ret[1]],a[ret[2]],a[ret[3]]))
{
return true;
}
return false;
}
double counts(int x)
{
int ret[4],p=1;
for(int i=1;i<=n;i++)
{
if(x>>(i-1)&1)
{
ret[p++]=i;
}
}
return getnum(a[ret[1]],a[ret[2]],a[ret[3]]);
}
int main()
{
sum[0]=1;
init();
while(scanf("%d",&n),n)
{
memset(dp,0,sizeof(dp));
double ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=(1<<3)-1;i<=(1<<n)-1;i++)
{
int num=cal(i);
if(!(num%3))
{
int k=num/3;
for(int j=1;j<=sum[k-1];j++)
{
int r=box[k-1][j];
if((r&i)==r)
{
if(okc(i^r))
{
dp[i]=max(dp[i],dp[r]+counts(i^r));
ans=max(ans,dp[i]);
}
}
}
}
}
printf("%.2f
",ans);
}
}