类似LIS的思想,只能用LIS的 O(n2)的算法,O(nlogn)的算法用不了,因为每个数值加了权值!其实我感觉可以用树形dp的,因为他们是偏序关系,可以建一个hash图,复杂度O(nlogn)绝对可以,然后dp过程只要O(n)的复杂度,可以每次判断hash图中被自己覆盖元素的最大的那个值,然后加上自己的权值,就能推出自己所能达到的最大值,这样dp只要扫一遍就可以了,总复杂度O(nlogn)。。。。。那个。。。有谁知道怎么建hash图不
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct pp
{
int x,y,h;
bool operator == (const pp& cmp) const
{
if(x==cmp.x && y==cmp.y)
{
return true;
}
else
{
return false;
}
}
bool operator < (const pp& cmp) const
{
if(x!=cmp.x)
{
return x<cmp.x;
}
else if(y!=cmp.y)
{
return y<cmp.y;
}
else
{
return h<cmp.h;
}
}
}p;
int a,b,c,N,ca,tmax,maxh,dp[200];
vector<pp>va,vb;
inline void pushinto()
{
p.x=a;
p.y=b;
p.h=c;
va.push_back(p); // a b c
swap(p.x , p.y);
va.push_back(p); // b a c
swap(p.y , p.h);
va.push_back(p); // b c a
swap(p.x , p.y);
va.push_back(p); // c b a
swap(p.y , p.h);
va.push_back(p); // c a b
swap(p.x , p.y);
va.push_back(p); // a c b
return ;
}
void uniquecopy()
{
sort(va.begin(),va.end());
vb.push_back(va[0]);
for(int i=1;i<va.size();i++)
{
if( va[i] == vb.back() )
{
if(va[i].h > vb.back().h)
{
vb.back().h = va[i].h;
}
}
else
{
vb.push_back(va[i]);
}
}
return ;
}
void dpstart()
{
memset(dp,0,sizeof(dp));
maxh=dp[0]=vb[0].h;
for(int i=1;i<vb.size();i++)
{
tmax=0;
for(int j=i-1;j>=0;j--)
{
if(vb[i].y > vb[j].y && vb[i].x != vb[j].x)
{
if(dp[j]>tmax)
{
tmax=dp[j];
}
}
}
dp[i]=vb[i].h+tmax;
if(dp[i]>maxh)
{
maxh=dp[i];
}
}
printf("Case %d: maximum height = ",ca++);
cout<<maxh<<endl;
return ;
}
int main()
{
ca=1;
while(cin>>N)
{
if(0 == N)
{
break;
}
va.clear();
vb.clear();
for(int i=1;i<=N;i++)
{
cin>>a>>b>>c;
pushinto();
}
uniquecopy();
dpstart();
}
return 0;
}
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版)
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
hdu_2102_passed_sorce
此程序为hdu的acm2010题,就是解决水仙花数问题
模式识别_hdu_期末复习资料集合_试卷笔记.zip
HDU_ACM_1002_大数相加C源代码,利用字符串处理
数字图像处理_hdu_期末复习资料_试卷等.zip
数字图像处理总ppt_hdu_许老师.pdf
高级计算机图形学_mm的_重点笔记_hdu_吴xy.pdf
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
B_(HDU_1231)(最大子段和,分治).cpp
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?...
hdu题解的答案十分简单的一个题,思路清晰,特别简单
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
hdu 3378 三国杀标程 解题报告
动态规划DP题解 POJ HDU部分动态规划DP题解
里面包含:实验1~8的源代码,ISE软件直接导入就能使用、课件PPT、3份实验报告、实验要求与评分标准。