Ural 1078 segement

爱被打了一巴掌 2022-08-11 06:29 140阅读 0赞

O(n^2)的动态规划的算法。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N=505;
    struct segement
    {
    	int s,t,id;
    	void read()
    	{
    		scanf("%d%d",&s,&t);
    	}
    	bool operator < (const segement &x)const{
    		if(s==x.s)return t<x.t;
    		else return s<x.s;
    	}
    }sege[N],tsege[N];
    
    int pre[N],arr[N];
    int main()
    {
    	int n;
    //	freopen("in.txt","r",stdin);
    	//freopen("out.txt","w",stdout);
    	while(scanf("%d",&n)==1)
    	{
    		int i,j;
    		for(i=1;i<=n;i++)
    		{
    			sege[i].read();
    			sege[i].id=i;
    		}
    		int a=0;
    		sort(sege+1,sege+n+1);
    		arr[1]=1;pre[1]=0;int ml=0,mlc=0;
    		for(i=2;i<=n;i++)
    		{
    			int coor=0,len=0;
    			for(j=1;j<i;j++)
    			{
    				if(sege[i].t<sege[j].t&&len<arr[j])
    				{
    					len=arr[j];coor=j;
    				}
    			}
    			arr[i]=len+1;pre[i]=coor;
    			if(ml<arr[i]){ml=arr[i];mlc=i;}
    		}
    		for(i=mlc,j=1;i;i=pre[i])
    		{
    			tsege[j]=sege[i];
    			j++;
    		}
    	//	tsege[j]=sege[i];
    	if(n==1){
    		printf("1\n1\n");continue;
    	}
    		printf("%d\n",ml);
    		for(i=1;i<=ml;i++)
    			printf("%d ",tsege[i].id);
    		putchar(10);
    	}
    //	system("pause");
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Ural 1078 segement

O(n^2)的动态规划的算法。 include <cstdio> include <cstring> include <cstdlib> in

爱被打了一巴掌/ 2022年08月11日 06:29/ 0 赞/ 141 阅读

相关 URAL--1007 codewords

三种信息传递过程中可能出错的方式，让你恢复原来正确的信息。我用的是分类暴搜，用字符串模拟的，这里还是是可行的，不过debug快坑死了o(╯□╰)o...... 后面还有一

落日映苍穹つ/ 2022年08月11日 00:44/ 0 赞/ 168 阅读

相关 URAL 1057 (数位dp)

问题描述: Create a code to determine the amount of integers, lying in the set \[ X; Y\] and

比眉伴天荒/ 2022年06月04日 05:16/ 0 赞/ 181 阅读

相关 URAL - 1056(DFS)

问题描述: Background Computer net is created by consecutive computer plug-up to one that h

Dear 丶/ 2022年06月04日 05:15/ 0 赞/ 169 阅读

相关 URAL 1036(数位dp)

问题描述: You are given a number 1 ≤ N ≤ 50. Every ticket has its 2 N-digit number. We call

矫情吗；*/ 2022年06月04日 05:15/ 0 赞/ 224 阅读

相关 Ural 1033 Labyrinth（bfs）

Administration of the labyrinth has decided to start a new season with new wallpapers. F

本是古典何须时尚/ 2022年06月03日 08:59/ 0 赞/ 172 阅读

相关 1078. Hashing (25)

The task of this problem is simple: insert a sequence of distinct positive integers into

红太狼/ 2022年05月29日 13:25/ 0 赞/ 114 阅读

相关 PAT A1078

![clipboard.png][] 这道题牵扯到了hash散列中的集中查询方式，随后做一个总结，对于素数方面，没有神马难度； include<iostream>

以你之姓@/ 2022年03月07日 00:20/ 0 赞/ 142 阅读

相关 URAL 1056. Computer Net

1056. Computer Net Time limit: 2.0 second Memory limit: 64 MB Background Computer

红太狼/ 2021年12月23日 19:11/ 0 赞/ 183 阅读

相关 URAL 1029

题目大意：M层N列的矩阵（各元素均为正整数），找出一个路径从第一层到达第M层，使得路径上的所有数的和是所有可达路径中最小的，每次上到下一层以后就不能再上去，依次输出路径上的各点

清疚/ 2021年12月14日 00:45/ 0 赞/ 233 阅读