P2889 [USACO07NOV] Milking Time S

题目大意

有 $N$ 个小时可以挤奶。其中有 $m$ 个时间段可以给 Bessis 奶牛挤奶。第 $i$ 个时间段为 $s_i$ ~ $t_i$，可以获得 $Ef{f}_i$ 滴奶。每次挤完奶后，人都要休息 $R$ 小时。最后问，一共能挤出多少滴奶。

双重选择分析

休息 $R$ 小时可以归为挤奶时间段内。即，第 $i$ 段挤奶的时间段为 $s_i$ ~ $t_i=t_i+R$。

设挤奶的最佳方案为：
{ a 1 , a 2 , . . . , a k } \{a_1,a_2,...,a_k\} {a1​,a2​,...,ak​}，其中 $a_i$ 是第 $i$ 个挤奶的时间段编号。同时满足 $s_{a_2}\ge t_{a_1}$，$s_{a_3}\ge t_{a_2}$，以此类推。

显然，为了更好的选奶牛，要对奶牛按 $t_i$ 进行排列。

对 $a_k$ 进行双重选择分析：

• 当 $a_k=m$，方案变为 { a 1 , a 2 , . . . , a k − 1 , m } \{a_1,a_2,...,a_{k-1},m\} {a1​,a2​,...,ak−1​,m}方案的属性：

  1. 奶量。原方案的奶量 = 子方案的奶量 + $Ef{f}_m$。由于，原方案求的是最大奶量，所以子方案求解的也是最大奶量。
  2. 可以选择的时间段范围。子方案可以选择的范围为 1 ~ $m-1$。
  3. 奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 $s_m$。

  综上，子方案反映的问题为，从 1 ~ $m-1$ 个时间段中，挤奶结束时间最大为 $s_m$ 的最大奶量问题。

• 当 $a_k\ne m$，方案不变。
  方案的属性：

  1. 奶量。原方案的奶量 = 子方案的奶量。
  2. 可以选择的时间段范围。子方案可以选择的范围为 1 ~ $m-1$。
  3. 奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 $N$。

  综上，子方案反映的问题为，从 1 ~ $m-1$ 个时间段中，挤奶结束时间最大为 $N$ 的最大奶量问题。

综上，原问题的状态描述为 $$d{p}_{m,N}$$状态转移式为 $$d{p}_{m,N}=\max (d{p}_{m-1,s_n}+Ef{f}_m,d{p}_{m-1,N})$$

将其一般化可得 $$d{p}_{i,j}=\max (d{p}_{i-1,s_i}+Ef{f}_i,d{p}_{i-1,j})$$需要注意的是：第一种情况只有当 $t_i\le j$ 的时候才成立。

这样做，最终的时间复杂度、空间复杂度都为 $O(nm)$，只能拿到 70 分。

示例程序

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e3 + 10;struct node{int s,t,eff;bool operator < (const node &p)const{return t < p.t;}
}cow[N];int dp[N][N * 100];int main(){int n,m,r;cin >> n >> m >> r;n += r;for(int i = 1; i <= m; i++){cin >> cow[i].s >> cow[i].t >> cow[i].eff;cow[i].t = cow[i].t + r;}sort(cow + 1,cow + m + 1);for(int i = 0; i <= n; i++){if(i >= cow[1].t) dp[1][i] = cow[1].eff;else dp[1][i] = 0;}for(int i = 2; i <= m; i++){for(int j = 0; j <= n; j++){if(j >= cow[i].t){dp[i][j] = dp[i - 1][cow[i].s] + cow[i].eff;}dp[i][j] = max(dp[i][j],dp[i - 1][j]);}}cout << dp[m][n];return 0;
}