首页 > 代码库 > HDU 1069 Monkey and Banana
HDU 1069 Monkey and Banana
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1069
解题思路:
这是LIS的变形。用O(n^2)的方法来解决这道题。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 const int MAXN=100000; 8 const int INF=1<<30; 9 int dp[MAXN]; 10 11 struct node{ 12 int x,y,w; 13 bool operator <(const node &rhs)const{ 14 if(x!=rhs.x) 15 return x<rhs.x; 16 else if(y!=rhs.y) 17 return y<rhs.y; 18 return w<rhs.w; 19 } 20 }S[MAXN]; 21 22 int tot=0; 23 void addS(int x,int y,int w){ 24 S[tot].x=x; 25 S[tot].y=y; 26 S[tot++].w=w; 27 } 28 29 int solve(){ 30 int res=-INF; 31 for(int i=0;i<tot;i++){ 32 dp[i]=S[i].w; 33 34 for(int j=0;j<i;j++) 35 if(S[i].x>S[j].x&&S[i].y>S[j].y) 36 dp[i]=max(dp[i],dp[j]+S[i].w); 37 res=max(dp[i],res); 38 } 39 return res; 40 } 41 42 int main(){ 43 int n; 44 int iCase=0; 45 while(scanf("%d",&n)!=EOF&&n){ 46 tot=0; 47 for(int i=0;i<n;i++){ 48 int x,y,w; 49 scanf("%d%d%d",&x,&y,&w); 50 51 addS(x,y,w); 52 addS(y,x,w); 53 54 addS(x,w,y); 55 addS(w,x,y); 56 57 addS(y,w,x); 58 addS(w,y,x); 59 } 60 sort(S,S+tot); 61 printf("Case %d: maximum height = %d\n",++iCase,solve()); 62 } 63 }
HDU 1069 Monkey and Banana
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。