wikioi 1214 线段覆盖 - c++编程基础

题目描述 Description

给定x轴上的N（0

输入描述 Input Description

输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述 Output Description

输出第一行是一个整数表示最多剩下的线段数。

样例输入 Sample Input

6 3

1 3

2 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

贪心解法：首先将线段端点调整为左端点小于（或等于）右端点；第二，根据右端点将线段从小到大排序；第三，扫描一遍，每次遇到的第一个与当前的max不想交的即为最优选择。

#include   
#include   
#include   
using namespace std;  
struct node {  
  int a,b;  
}x[100];  
int cmp(node x1, node x2)  
{  
  return x1.b < x2.b;  
}  
int main()  
{  
  int n;  
  cin >> n;  
  for(int i=0; i> x[i].a >> x[i].b;  
    if(x[i].a>x[i].b) swap(x[i].a, x[i].b);  
  }  
  sort(x, x+n, cmp);  
  int res = 0, max = -1000;  
  for(int i=0; i




= max)  
    {  
      res++;  
      max = x[i].b;  
    }  
  }  
  cout << res;  
  return 0;  
}

序列型动态规划（DP）：前两步同上，第三步，dp[i] = max(dp[i], (dp[j]+1))。第四，选择dp数组中最大值即为结果。

#include   
#include   
using namespace std;  
  
int main()  
{  
  int n,a[100],b[100],dp[100];  
  cin >> n;  
  for(int i=0; i> a[i] >> b[i];  
    if(a[i]>b[i])  
    {  
      int t = a[i];  
      a[i] = b[i];  
      b[i] = t;  
    }  
  }  
  for(int i=n-1; i>0; i--)  
  {  
    for(int j=0; jb[j+1])  
      {  
        int t = b[j];  
        b[j] = b[j+1];  
        b[j+1] = t;  
        t = a[j];  
        a[j] = a[j+1];  
        a[j+1] = t;  
      }  
    }  
  }  
    
  int max = 0;  
  for(int i=1; i=b[j])  
        dp[i] = dp[i]>(dp[j]+1) dp[i]:(dp[j]+1);  
        if(max < dp[i]) max = dp[i];  
        //cout << "i:" << i << " j:" << j << " dp[i]:" << dp[i] <<" dp[j]:" << dp[j] << endl;  
    }  
  }

cout << max;

return 0;

}