# Zerojudge f173 作物種植
{%hackmd @fishhh/style %}

###### tags: `競程題解`,`競程`
Timestamp ： 2022/11/30 21:10

題目：
> 給你 $T$ 個區間，選一些區間，不能重疊，最大的區間長度和

範圍：
> $1\leq T \leq 10^4$
> $1\leq m \leq 10^4$

題解：去看我 [解題報告](https://zerojudge.tw/ShowThread?postid=33102&reply=0)

:::spoiler code

#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;
#define pii pair<int,int>
int get()
{
    char ch;int x=0;int p=1;
    ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    if(ch=='-')p=-1;
    while(ch>='0' && ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return p*x;
}
int dp[2][10010]={}; //idx1-> last_dis idx2-> last_v_idx
int main(){
    int m,t;
    m=get(),t=get();
    vector<pii> v(t);
    for(auto &i:v){
        i.first=get(),i.second=get();
    }
    sort(v.begin(),v.end());

    int ans=0;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=m;j++){
            if(j>=v[i-1].second){
                dp[i%2][j]=max(dp[1-(i%2)][j],dp[1-(i%2)][v[i-1].first]+(v[i-1].second-v[i-1].first));
            }
            else{
                dp[i%2][j]=dp[1-(i%2)][j];
            }
            // ans=max(dp[i][j],ans);
        }
    }

    cout<<dp[t%2][m];
}

:::