点击打开链接poj 1948
思路: 二维0/1背包
分析:
1 题目要求从n个木棒里面选出m个组成一个三角形,使得三角形的面积最大
2 对于三角形来说知道了两条边和周长就可以求面积,按照0/1背包的思想dp[i][j][k]表示前i个木棒能否组成第一条边为长度j,第二条长度为k。如果dp[j-v[i]][k] 或dp[j][k-v[i]] 为true则dp[j][k]就为true
3 我们求出了所有可能的组合之和,就去枚举所有的边长的情况,然后求最大的面积
代码:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 45;
const int MAXN = 2010;
int n , sum , v[N];
bool dp[MAXN][MAXN];
int solve(){
memset(dp , false , sizeof(dp));
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i++){
for(int j = sum/2 ; j >= 0 ; j--){ // 最大的边长为周长的一半
for(int k = j ; k >= 0 ; k--){// 两条边存在大小的关系,所以直接让k <= j 即可
if(j >= v[i] && dp[j-v[i]][k])
dp[j][k] = true;
if(k >= v[i] && dp[j][k-v[i]])
dp[j][k] = true;
}
}
}
int ans;
ans = -1;
for(int j = 1 ; j <= sum/2 ; j++){
for(int k = 1 ; k <= j ; k++){// 由于上面是j >= k,这里k枚举到j
int t = sum-j-k;
if(dp[j][k] && t > 0 && j+k > t && j+t > k && t+k > j){
// 注意由于求最大的面积,这边求p注意,求tmp的时候才转化为int
double p=(t+j+k)/2.0;
int tmp=(int)(sqrt(p*(p-t)*(p-j)*(p-k))*100);
ans = max(ans , tmp);
}
}
}
return ans;
}
int main(){
while(scanf("%d" , &n) != EOF){
sum = 0;
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &v[i]);
sum += v[i];
}
printf("%d\n" , solve());
}
return 0;
}
分享到:
相关推荐
晒代码之二——多重背包(POJ1276)
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2676-Sudoku 解题报告+AC代码
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1747400
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
<1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造三角形问题 带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
网上整理的一些poj刷题指南。 poj地址:http://poj.org
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj2009离线题库 poj2009离线题库
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ3414-Pots 解题报告+AC代码