wikioi 3027 线段覆盖 2

题目描述 Description

数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。

n<=1000

输入描述 Input Description

第一行一个整数n，表示有多少条线段。

接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。

输出描述 Output Description

输出能够获得的最大价值

样例输入 Sample Input

1 2 1

2 3 2

1 3 4

样例输出 Sample Output

觉得这道题是最长递增子序列，因为可以用跟线段覆盖一样的预处理，按右节点递增排序，然后问题就转换为最长递增子序列了，w[i] 表示排好序后第 i 个线段的价值，dp[i] 表示当前的前 i 个线段所能获得最大价值，而

dp[i] = max{ dp[j] + w[i] } ( 1 <= j < i )

	
/*
  作者:t_rex
  题目:p3027 线段覆盖 2
*/
#include <iostream>
using namespace std;
int k[1000][3];
int w[1000];
void quicksort(int a[][3], int b, int e){
    //快速排序
    if(b >= e)
        return;
    int i = b, j = e + 1, n, m, k;
    int x = a[i][1], y = a[i][0], z = a[i][2];
    while(true){
        while(a[++i][1] < x && i < j);
        while(a[--j][1] > x);
        if(i >= j)
	        break;
        else{
	        n  = a[i][0], m = a[i][1], k = a[i][2];
	        a[i][0] = a[j][0], a[i][1] = a[j][1], a[i][2] = a[j][2];
	        a[j][0] = n, a[j][1] = m, a[j][2] = k;
        }
    }
    a[b][0] = a[j][0], a[b][1] = a[j][1], a[b][2] = a[j][2];
    a[j][0] = y, a[j][1] = x, a[j][2] = z;
    quicksort(a, j+1, e);
    quicksort(a, b, j-1);
}


int main(){
    int n, i = 0, a, b, c, j, max_val = 0;
    cin >> n;
    for(; i < n; i++){
	    cin >> a >> b >> c;
	    if(a < b) swap(a, b);
	    k[i][0] = b, k[i][1] = a, k[i][2] = c;
    }
    quicksort(k, 0, n-1);
    for(i = 0; i < n; i++) w[i] = k[i][2];
    for(i = 1; i < n; i++){
	    for(j = 0; j < i; j++){
	        if(k[j][1] <= k[i][0] && w[j] + k[i][2] > w[i]) w[i] = w[j] + k[i][2];
	        max_val = max(max_val, w[i]);
	    }
    }
    cout << max_val ;
    return 0;
}

wikioi 3027 线段覆盖 2

推荐阅读