P1868 饥饿的奶牛

Problem

给定(n)个闭区间([x_i,y_i])，要选若干个区间，使其区间长度和最大，且无交集。
(n le 1.5 imes 10^5,1 le x_i,y_i le 3 imes 10^6)

Solution

设(m = max {y_i})。
设(dp_i)为([i,n])中的最大数,(g_i)为以(i)为左端点的区间的序号,(len_i)表示第(i)个区间的长度。则

[dp_i = egin{cases} dp_{i + 1} & g_i = emptyset \ max (dp_{i + 1},max_{j in g_i} {dp_{i + len_j} + len_j} ) & g_i eq emptyset end{cases} ]

# include <bits/stdc++.h>
using namespace std;
const int N = 1500005,M = 3e6 + 5;
int n;
pair<int,int> a[N];
vector <int> g[N];
int dp[M];
int Left[M],Right[M],len[N];
int m;
int main(void)
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d",&a[i].first,&a[i].second);
        g[a[i].first].push_back(i);
        len[i] = a[i].second - a[i].first + 1;
        m = max(m,a[i].second);
    }
    for(int i = m; i >= 1; i--)
    {
        dp[i] = dp[i + 1];
        if(g[i].size())
        {
            for(int j = 0; j < (int)g[i].size(); j++)
            {
                dp[i] = max(dp[i],dp[i + len[g[i][j]]] + len[g[i][j]]);
            }
        }
    }
    printf("%d
",dp[1]);
    return 0;
}