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

最新文章

热门文章