hdu5135 Little Zu Chongzhi's Triangles（DP）
分类：
该题其实是个DP，可能数据比较水，队友排序后从大的开始取都过了。。
我们来说说正解，一开始其实我已经写出来了，只是有一个地方导致了一直在输出一个不是数字的值，赛后才发现是我用memset对一个double类型的数组清-1的原因 ，改了一下就对了 。 直接开一维数组，用二进制表示集合的方法来表示哪些木棍被选取了 。 很简单的状态压缩DP 。
另外需要注意一点： 位运算符的优先级比较低，，所以在不确定的情况下要多加括号 ~
我用的记忆化搜索，该题还可以用三重循环地推的方式求 。
细节参见代码 ：
#include <bits/stdc++.h>using namespace std;const double INF = -1000000000;int n,kase = 0,vis[1<<13];double a[13],d[1<<13];bool issan(double a, double b, double c) { //判断能否构成三角形if(a+b>c&&a+c>b&&b+c>a)return true;return false;}double Sa(double a, double b, double c) { //公式求面积double s = (a+b+c)/2;double ans = sqrt((a+b+c)*(a+b-c)*(a+c-b)*(b+c-a))/4.0;return ans;}double dp(int S) {double& ans = d[S];if(vis[S] == kase) return ans;vis[S] = kase;ans = 0;for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {for(int k=0;k<n;k++) {if(i!=j&&i!=k&&j!=k && issan(a[i],a[j],a[k])) {if((S & (1<<i)) && (S & (1<<j)) && (S & (1<<k)) ) {int s = S ^ (1<<i);s = s ^ (1<<j);s = s ^ (1<<k);ans = max(ans,dp(s)+Sa(a[i],a[j],a[k]));}}}}}return ans;}int main() {while(~scanf("%d",&n)&&n) {for(int i=0;i<n;i++) scanf("%lf",&a[i]);++kase;double ans = dp((1<<n) – 1);printf("%.2f\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇ZOJ Problem Set – 3811 Untrusted Patrol下一篇225 – Golygons（暴力搜索）
顶1踩0
没有什么可留恋，只有抑制不住的梦想，没有什么可凭仗，
