上课作业(5)——＃576. 饥饿的牛(hunger)

目录

Description

Format

Input

Output

Samples

输入数据 1

输出数据 1

Limitation

题解：

状态转移方程：

程序：

Description

牛在饲料槽前排好了队。饲料槽依次用 1 到 N(1≤N≤2000) 编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。

约翰提供 B 个区间的清单。一个区间是一对整数 start−end(1≤start≤end≤N)，表示一些连续的饲料槽，比如 1-3,7-8,3-4 等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。

当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。

在上面的例子中，1-3 和 3-4 是重叠的；聪明的牛选择 {1-3，7-8}，这样可以吃到 5 个槽里的东西。

Format

Input

第 1 行，整数 B(1≤B≤1000)。

第 2∼B+1 行，每行两个整数，表示一个区间，较小的端点在前面。

Output

仅一个整数，表示最多能吃到多少个槽里的食物。

Samples

输入数据 1

3
1 3
7 8
3 4

输出数据 1

5

Limitation

1s, 1024KiB for each test case

题解：

类似于演讲大厅安排，思路也差不多，就是开个结构体变为0/1背包，循环时注意要从下标位0开始遍历。

状态转移方程：

dp[j]=max(dp[j],dp[a[i].s-1]+a[i].h);//状态转移方程 

程序：

#include <bits/stdc++.h>
using namespace std;
int n,dp[2010];
struct H{
    int s,e,h;//s是区间的第一个食槽下标，e是区间的最后一个食槽下标，h是区间的食槽数
}a[2010];
bool cmp(H x,H y){//排序判断条件
    return x.e<y.e;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){//输入区间的第一个食槽下标和区间的最后一个食槽下标并计算出区间的食槽数
        cin>>a[i].s>>a[i].e;
        a[i].h=a[i].e-a[i].s+1;
    }
    sort(a,a+n,cmp);//排序
    for(int i=0;i<n;i++){//遍历每个食槽区间
        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);//状态转移方程 
    }
    cout<<dp[a[n-1].e];
    return 0;
}