HDU 1160 FatMouse's Speed (DP)

深藏阁楼爱情的钟 2022-06-03 05:00 122阅读 0赞

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

根据题意的意思就是要先将数据按体重递增，速度递减排序后找最长子序列。

所以推荐用sort函数排好后循环判断就好。

不过题目要求的是输出数据的位置，所以还要定义一个结构体去储存下。

//题意自己看，不会度娘

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    using namespace std; 
    struct node
    {
    	int w;
    	int s;
    	int flag; 
    }a[1005];
    struct node1
    {
    	int num;
    	int count;
    }dp[1005];
    bool cmp(node a,node b)
    {
    	if(a.w==b.w)
    		return a.s>b.s;
    	return a.w<b.w;
    }
    int main(int argc, char *argv[])
    {
    	int max,t;
    	int i,j,k;
    	i=0;
    	while(scanf("%d %d",&a[i].w,&a[i].s)!=EOF)
    	{
    		a[i].flag=i+1;
    		i++;
    		//printf("*%d",i); 
    	}		
    	sort(a,a+i,cmp);
    	//printf("*1\n");
    	for(j=0;j<i;j++)
    	{
    		dp[j].num=1;
    		dp[j].count=0;		
    	}
    	max=1;
    	t=1;
    	for(j=1;j<i;j++)
    	{
    		for(k=0;k<j;k++)
    		{
    			if(a[j].s<a[k].s&&a[j].w>a[k].w)
    			{
    				if(dp[j].num<dp[k].num+1)
    				{	
    					dp[j].num=dp[k].num+1;
    					dp[j].count=k;
    				} 
    			}
    		}	
    		if(dp[j].num>max)
    		{
    			max=dp[j].num;
    			t=j;	
    		}
    	}	
    	printf("%d\n",max);
    	int m[1005];
    	for(j=1;j<=max;j++)
    	{
    		m[j]=t;
    		t=dp[t].count;
    	}	
    	for(k=max;k>=1;k--)
    		printf("%d\n",a[m[k]].flag); 
    	return 0;
    }

//Start-ZJ

//2017/12/19/10:38

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 174 阅读

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

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

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

相关 HDU 1160 FatMouse's Speed (DP)

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

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

相关 HDU-FatMouse' Trade （贪心）

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

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

相关【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 赞/ 202 阅读

相关 HDU 1009 FatMouse' Trade

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

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

相关 HDU 1160 FatMouse's Speed

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

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

相关 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 赞/ 193 阅读

相关 hdu1160

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

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

相关 HDU 1078 FatMouse and Cheese（记忆化搜索，DP）

目录 1.题目 2.题意 3.思路 4.代码 1.题目 Fa

╰+哭是因爲堅強的太久メ/ 2021年08月29日 00:50/ 0 赞/ 330 阅读