题解 P1868 【饥饿的奶牛】

zhy137036 · 2020-02-28 20:20:45 · 题解

这篇题解记录了我做这道题的思考过程。

题意简述

• 给你 n 个区间 (x,y)，长度为 y-x+1。
• 选择不相交的几个区间，使长度之和最大。
• 两个区间 (x_1,y_1) 和 (x_2,y_2) 不相交，当且仅当 y_1<x_2 或 y_2<x_1。

题目分析

有人曾经说过：你不会的题很可能就是动态规划。

这道题就是动态规划。

区间？感觉是线性动态规划，再看数据范围，没错了。

状态定义

首先不妨想象这些草地是一个一个的格子。

先从最简单的定义想起：

设 f_i 表示前 i 个格子最多能吃到多少牧草。

虽然这个定义很简单，但是很好用。

转移式

显然 f_j\ge f_{j-1}。多一个格子选择，吃得总不会更少。

如果有一个区间 (i,j)，那么 f_j\ge f_{i-1}+j-i+1。

最后得到转移式：

细节处理

但是怎么对于所有的 j 都知道对应的所有的 i 呢？

发现一个 j 所对应的 i 的个数是不固定的，所以想到用 std::vector<int> 保存。

代码

自认为代码比较简洁。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>beg[3000010];//有点大，不过并不会 MLE
int n,mx,f[3000010];//mx 代表最大的 y，f 就是 dp 用的数组
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        beg[y].push_back(x-1);//这里保存的是 x-1，后面会比较方便
        mx=max(mx,y);
    }
    for(int i=1;i<=mx;i++){
        f[i]=f[i-1];//先设定为 f[i-1]，后面再更新
        for(int j=0;j<beg[i].size();j++){
            int b=beg[i][j];
            f[i]=max(f[i],f[b]+i-b);//这里会比较方便
        }
    }
    printf("%d\n",f[mx]);
    return 0;
}