我在动态编程问题上苦苦挣扎了几天。它是这样的：John 的工作日被划分为 N 个时隙，每个时隙 i 都关联一个增益 G[i]，如果他在那个时隙工作，他可以获得的收益 G[i]。如果他决定在时间间隔 [i, j] 内工作，他的总奖励将是 R[i,j]=G[i+1]+...+G[j]，因为第一个时间段用于热身。每天他必须准确地工作 T 个时隙——他可以从可用的 N 个总时隙中选择 T 个时隙的子集。他想通过选择一组分离区间 [a1,b1], [a2,b2], ...[ak,bk] 来最大化他的利润，其中 1 <= a1 <= b1 < a2 <= b2 <... < ak <= bk 和 Sum[i=1, k](bi-ai+1)=T。
示例：N=7，T=5，增益向量 {3,9,1,1,7,5,4}。最佳解决方案是选择区间 [1,2] 和 [4,6]，总利润为 9+12=21。
DP解：int f[i][j][0..1]；
let f[i][j][0] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is not used.
let f[i][j][1] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is used.
obviously,f[i][j][k] can determine f[i+1][j][k] or f[i+1][j+1][k]. details below:
f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]);
f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);