HDU 1160 FatMouse's Speed

电玩女神 2022-04-15 02:25 129阅读 0赞

## 原题目链接：[HDU1160][] ##

--------------------

## 分类 ##

HDU 动态规划 最长上升子序列

--------------------

## 题意 ##

给出老鼠的体重和速度

求最长的序列，使得体重递增，速度递减

--------------------

## 想法 ##

最长上升子序列变形

还有他加上了一个并查集求最长上升子序列路径的东西

--------------------

## 代码 ##

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/18 */
    #include <bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn = 1111; 
    
    int dp[maxn];
    int pre[maxn];
    struct A{ 
    	int w,s,id;
    }E[maxn];
    
    bool cmp(A a,A b){ 
    	return a.w > b.w;
    }
    
    int main()
    { 
    	int k=0;
    	while(scanf("%d%d",&E[k].w,&E[k].s)!=-1){ 
    		E[k].id=k+1;
    		k++;
    	}	
    	memset(pre,-1,sizeof(pre));
    	sort(E, E+k,cmp);
    	for(int i=0; i < k;i++)
    		dp[i] = 1;
    	
    	for(int i=0;i<k;i++){ 
    		for(int j=0;j < i;j++)
    		{ 
    			if(E[i].w < E[j].w && E[i].s > E[j].s){ 
    				if(dp[i] < dp[j] + 1){ 
    					dp[i] = dp[j] + 1;
    					pre[i] = j;
    				}
    			}
    		}
    	}
    	int ans=0;
    	int p;
    	for(int i=0;i<k;i++)
    	{ 
    		if(dp[i]>ans)
    		{ 
    			ans=dp[i];
    			p=i;
    		}		
    	}
    	printf("%d\n",dp[p]);
    	while(p!=-1)
    	{ 
    		printf("%d\n",E[p].id);
    		p=pre[p];
    	}
        return 0;
    }

--------------------

[HDU1160]: http://acm.hdu.edu.cn/showproblem.php?pid=1160

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 1009 FatMouse' Trade

FatMouse' Trade Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

灰太狼/ 2022年06月16日 12:54/ 0 赞/ 135 阅读

相关 J - FatMouse's Speed HDU - 1160——基础dp

Think: 1知识点：排序+最长上升子序列+记录路径 2题意：寻找一个最长子串，使得重量w严格递增，速度c严格递减 3反思：注意排序后的路径记录和通过递归回溯输出

我不是女神ヾ/ 2022年06月10日 03:41/ 0 赞/ 87 阅读

相关 HDU 1160 FatMouse's Speed (DP)

这道题的思路想通了就很简单。不需要DP转移公式，想多了，一直想推出来反而写错了。明明刘春英讲DP的时候已经想通了还是会错，还是练得少啊。根据题意的意思就是要先将数据按体重递

深藏阁楼爱情的钟/ 2022年06月03日 05:00/ 0 赞/ 97 阅读

相关 HDU-FatMouse' Trade （贪心）

FatMouse' Trade Problem Description FatMouse prepared M pounds of cat food,

心已赠人/ 2022年05月26日 04:22/ 0 赞/ 132 阅读

相关【1009 HDU】FatMouse' Trade

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1009][http_acm.hdu.edu.cn_showproblem.ph

痛定思痛。/ 2022年05月13日 06:18/ 0 赞/ 172 阅读

相关 HDU 1009 FatMouse' Trade

原题目链接[HDU1009][] -------------------- 分类 HDU 贪心 -------------------- 题意贪心专题

末蓝、/ 2022年04月16日 04:59/ 0 赞/ 148 阅读

相关 HDU 1160 FatMouse's Speed

原题目链接：[HDU1160][] -------------------- 分类 HDU 动态规划最长上升子序列 --------------------

电玩女神/ 2022年04月15日 02:25/ 0 赞/ 130 阅读

相关 HDU-1009——FatMouse' Trade

[ FatMouse' Trade][FatMouse_ Trade] Problem D

「爱情、让人受尽委屈。」/ 2022年04月11日 09:54/ 0 赞/ 146 阅读

相关 HDU-1160 FatMouse's Speed

链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_

╰半橙微兮°/ 2021年11月01日 14:46/ 0 赞/ 160 阅读

相关 hdu1160

[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_pid

￡神魔★判官ぃ/ 2021年10月19日 11:12/ 0 赞/ 183 阅读