DP+路径回溯 timus 1078. Segments URAL 解题报告
题目大意：给一些线段，并且每个线段都有左右点的坐标（数轴上的坐标），类似于求最大上生序列一样，求一个上升的最长序列，所为上升就是后一个 线段的左右下标包含前一个的范围，不能相等（coincide [,kəʊɪn'saɪd] vi. 一致，符合；同时发生） ；
类似于求最大上升序列，只不过判断条件多了一条，先对一条排序，然后dp[i]=max(dp[i][,dp[j]), j<i 再判断是再加一个前提是线段i包含j…… 如果i由j转移过来的，path[i]=j ，初始化path[i]=i; 然后从最大的dp开始回溯path，放到一个栈里，最后输出来即可！
此题没什么坑，注意边界条件就好，注意栈溢出等……
另外一种路径回溯，请戳并查看该题：D - Mysterious Present
#include<stack>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(i = (a); i < (b); ++i)
#define FORE(i,a,b) for(i = (a); i <= (b); ++i)
#define FORDE(i,a,b) for(i = (a); i >= (b); --i)
#define mem(a,val) memset(a,val,sizeof(a));
int n, s, ts;
int dp[510];
int path[510];
struct Node
{
int l,r;
int no;
}nod[510];
bool cmp(Node n1,Node n2)
{
if(n1.l!=n2.l)return n1.l>n2.l;
return n2.r<n2.r;
}
bool isok(Node n1,Node n2)
{
// cout<<n1.l<<" "<<n1.r<<" n2"<<n2.l<<' '<<n2.r<<endl;
if(n1.l<n2.l&&n1.r>n2.r){ return 1;}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&nod[i].l,&nod[i].r);
nod[i].no=i;
}sort(nod+1,nod+n+1,cmp);
mem(dp,0);
// mem(path,0);
dp[1]=1;path[1]=1;
int mmax=1,ind=1;
for(int i=2;i<=n;++i)
{
dp[i]=1;path[i]=i;
for(int j=i-1;j>=1;--j)
{
if(isok(nod[i],nod[j])&&dp[i]<dp[j]+1){dp[i]=dp[j]+1; path[i]=j;}
}
if(dp[i]>mmax)
{
mmax=dp[i],ind=i;
}
}
///路径回溯,两种回溯方法，这是其中之一，另一种是sumy和celadon的递归
stack <int> sta;
while(path[ind]!=ind)///如果相等就是自身指向自身，解释最后一个节点
{
sta.push(nod[ind].no);
ind=path[ind];
}sta.push(nod[ind].no);///把最后一个节点的序号（当做名字更好理解）放到栈里面,或者直接把ind放到栈里没输出的时候再做处理
cout<<sta.size()<<endl;
while(sta.size()>1)
{
printf("%d ",sta.top());sta.pop();
}if(sta.size()==1)printf("%d\n",sta.top()),sta.pop();
return 0;
}
1078. Segments
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
A number of segments are lying on a line. Every segment is given with the coordinates of its endpoints. Segments are numbered from 1 to N (0 < N < 500). We assume, that one segment
is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained
in. In the sequence, every segment except the last is inside the next segment in the sequence.
is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained
in. In the sequence, every segment except the last is inside the next segment in the sequence.
Input
The first line contains one integer N. Next, there are N lines, with two integers on every line, which are the coordinates of the left and the right endpoints of the corresponding
segment. These coordinates are integers in the interval [–10000, 10000]. We assume that, the given segments are numbered according to their place in the input.
segment. These coordinates are integers in the interval [–10000, 10000]. We assume that, the given segments are numbered according to their place in the input.
Output
The first line must contain one integer, equal to the number of segments in the found sequence. The following line must contain the numbers of the segments in this sequence. These numbers must be outputted,
in the order in which the segments' lengths increase, starting from the smallest. If there are more than one output sequences, write any of them.
in the order in which the segments' lengths increase, starting from the smallest. If there are more than one output sequences, write any of them.
Sample
| input | output |
|---|---|
4 -2 2 -1 1 -3 3 4 5 |
3 2 1 3 |