codevs3027 线段覆盖2(DP)

题目描述 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

数据范围及提示 Data Size & Hint

数据范围

对于40%的数据，n≤10；

对于100%的数据，n≤1000；

0<=ai,bi<=1000000

0<=ci<=1000000

这题比前一题（1214线段覆盖）多了一个线段的价值，要求价值最大，因此不能直接贪心。

按照终点排序，这样当确定线段i的时候，就只需要考虑它前面的线段。

d[i][0]表示不选第i条线段时前i条的最大价值，d[i][1]表示选第i条线段时前i条线段的最大价值。

这样有

d[i][0] = max( d[i-1][0], d[i-1][1] )

d[i][1] = max( d[j][0], d[j][1] ) + c[j] , 其中j表示前i条线段中不与i覆盖的最后一条

最后的答案是 max( d[n][0], d[n][1] )。

#include<iostream>
#include<cassert>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<iterator>
#include<cstdlib>
#include<vector>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define rep(i,f,t) for(int i = (f),_end_=(t); i <= _end_; ++i)
#define rep2(i,f,t) for(int i = (f),_end_=(t); i < _end_; ++i)
#define dep(i,f,t) for(int i = (f),_end_=(t); i >= _end_; --i)
#define dep2(i,f,t) for(int i = (f),_end_=(t); i > _end_; --i)
#define clr(c, x) memset(c, x, sizeof(c) )
typedef long long int64;
const int INF = 0x5f5f5f5f;
const double eps = 1e-8;
//*****************************************************
const int maxn = 1005;
struct Node
{
    int a,b,c;
    bool operator< (const Node &n2)const{return b < n2.b;}
}x[maxn];</p><p>int d[maxn][2];
bool cover(int i,int j){                 //i > j的情况下,返回线段ij是否覆盖
    return x[i].a < x[j].b;
}
int main()
{
    int n;
    x[0].b = x[0].a = -1;                 //0号下标做哨兵,防止while循环越界
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);
    sort(x+1,x+n+1);
    d[1][1] = x[1].c;
    for(int i = 2; i <= n; ++i)
    {
        d[i][0] = max(d[i-1][1], d[i-1][0]);
        int j = i-1;
        while(cover(i,j))--j;
        d[i][1] = max(d[j][0], d[j][1]) + x[i].c;
    }
    cout<<max(d[n][0], d[n][1])<<endl;
    return 0;
}