线性dp问题 背包选择问题
要选取得对象是牛的挤奶时段
根据之前的(人人都写过的)贪心问题,要按结束时间尽可能早的奶牛来选取
因此我们按结束时间来排序
从1到m开始枚举
对每头当前牛,选取之前与它无重叠时间段的牛的dp值取max
状态表示——dp i 前i头牛的最大效率
状态计算——dp i = dp i - 1,dp j + cow[i].w
注意初始化时,将0号位r初始化为负无穷,以对应初始只选当前牛的情况
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
struct COW {
int l, r, w;
bool operator < (const COW& a)const {
return r < a.r;
}
}cow[N];
int dp[N];
int n, m, k;
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
cin >> cow[i].l >> cow[i].r >> cow[i].w;
}
sort(cow+1, cow +m+1);
cow[0].r = -INF;
for (int i = 1; i <= m; i++)
for (int j = 0; j < i; j++)
if (cow[j].r + k <= cow[i].l)
dp[i] = max(dp[i - 1], dp[j] + cow[i].w);
cout << dp[m] << endl;
return 0;
}