Ural 1078 segement

爱被打了一巴掌 2022-08-11 06:29 159阅读 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 条评论，159人围观）

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

相关阅读

相关 1078. Bigram 分词

给出第一个词 `first` 和第二个词 `second`，考虑在某些文本 `text` 中可能以 "`first second third`" 形式出现的情况，其中 `sec

╰+哭是因爲堅強的太久メ/ 2023年10月04日 08:24/ 0 赞/ 5 阅读

相关 PAT甲级1078 hashing

题目大意：利用除留余数法建hashtable，然后利用平方探查法缓解hash值冲突问题，然后要你输出每个输入的值在hashtable中的下标位置，如果不存在的话输出 -

深碍√TFBOYSˉ_/ 2023年07月24日 13:13/ 0 赞/ 21 阅读

相关 LIGHTOJ-1078 - Integer Divisibility

1078 - Integer Divisibility <table> <tbody> <tr> <td title="normal judge" styl

阳光穿透心脏的1/2处/ 2022年08月18日 02:07/ 0 赞/ 23 阅读

相关 Ural 1078 segement

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

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

相关 URAL--1007 codewords

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

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

相关 URAL - 1056(DFS)

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

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

相关 1078. Hashing (25)

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

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

相关 Integer Divisibility LightOJ - 1078

If an integer is not divisible by 2 or 5, some multiple of that number in decimal notati

红太狼/ 2022年05月19日 13:41/ 0 赞/ 131 阅读

相关 PAT A1078

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

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

相关 URAL 1029

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

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