eduCF#61 C. Painting the Fence /// DP 选取k段能覆盖的格数

题目大意：

给定n m

接下来给定m个在n范围内的段的左右端 l r

求选取m-2段 最多能覆盖多少格

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define inc(i,l,r) for(int i=l;i<=r;i++)

#define dec(i,r,l) for(int i=r;i>=l;i--)

const int N=5e3+;

int n, m, L[N], dp[N];

// L[i] 表示 所有画到i的段中 l最左的一段的左端

// dp[i] 表示到i为止 选出当前k段 的最优解

int main()

{

    while(~scanf("%d%d",&n,&m)) {

        inc(i,,n) L[i]=i+, dp[i]=;

        // L[]置为i+1是为了表示没有被画过的状态

        inc(i,,m) {

            int l,r; scanf("%d%d",&l,&r);

            inc(j,l,r) L[j]=min(L[j],l);

        }

        inc(k,,m-) {

            dec(i,n,) dp[i]=max(dp[L[i]-]+i-L[i]+,dp[i]);

            // L[i]~i的一段都被画了 长度为 i-L[i]+1

            // 所以 dp[L[i]-1] 加上 L[i]到i被画的一段 更新dp[i]

            inc(i,,n) dp[i]=max(dp[i],dp[i-]);

            // 短的段存在更优的方案 自然可以更新长的段

        }

        printf("%d\n",dp[n]);

    }

    return ;

}

eduCF#61 C. Painting the Fence /// DP 选取k段能覆盖的格数的相关教程结束。