Class homework (5) -- 576. Hungry cattle

Catalog

Description

Format

Input

Output

Samples

input data 1

Output data 1

Limitation

Answer key ：

State transition equation ：

Program ：

Description

The cattle line up in front of the feed trough . The feed trough is used in turn 1 To N(1≤N≤2000)  Number . Every night , A lucky cow according to John's rules , Eat some of the feed in the trough .

John offers  B A list of intervals . An interval is a pair of integers start−end(1≤start≤end≤N), It means some continuous feed tanks , such as 1-3,7-8,3-4 wait . Cattle can choose any range , But the range chosen by cattle cannot overlap .

Of course , Cattle hope they can eat as much as possible . Give some intervals , Help the cow find some ranges , Make it eat the most .

In the example above ,1-3 and 3-4 It's overlapping ; Smart cattle choose {1-3,7-8}, So you can eat 5 Something in a slot .

Format

Input

The first  1 That's ok , Integers B(1≤B≤1000).

The first 2∼B+1  That's ok , Two integers per line , Represents an interval , The smaller endpoint is in front .

Output

Only one integer , It indicates the maximum number of food in the trough .

Samples

input data 1

3
1 3
7 8
3 4

Output data 1

5

Limitation

1s, 1024KiB for each test case

Answer key ：

Be similar to Arrangement of the lecture hall , The idea is similar , That is to open a structure and change it into 0/1 knapsack , When looping, pay attention to the subscript 0 To traverse the .

State transition equation ：

dp[j]=max(dp[j],dp[a[i].s-1]+a[i].h);// State transition equation  

Program ：

#include <bits/stdc++.h>
using namespace std;
int n,dp[2010];
struct H{
    int s,e,h;//s Is the subscript of the first trough of the interval ,e Is the subscript of the last trough of the interval ,h Is the number of slots in the interval 
}a[2010];
bool cmp(H x,H y){// Sorting criteria 
    return x.e<y.e;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){// Input the subscript of the first trough of the interval and the subscript of the last trough of the interval, and calculate the number of trough of the interval 
        cin>>a[i].s>>a[i].e;
        a[i].h=a[i].e-a[i].s+1;
    }
    sort(a,a+n,cmp);// Sort 
    for(int i=0;i<n;i++){// Traverse each trough section 
        for(int j=a[n-1].e;j>=a[i].e;j--)
            dp[j]=max(dp[j],dp[a[i].s-1]+a[i].h);// State transition equation  
    }
    cout<<dp[a[n-1].e];
    return 0;
}