任务执行策略
【题目描述】我们有一批任务在 mesos 当中。这批任务要么不依赖其它任务，要么一定恰好依赖于两个任务，并且整个依赖关系会构成一个三角模型：
Job(1, 1)
Job(2, 1) Job(2, 2)
Job(3, 1) Job(3, 2) Job(3, 3)
……
Job(n, 1) Job(n, 2) …… Job(n, n)
如上图，Job(1, 1) 依赖于 Job(2, 1) 和 Job(2, 2)；Job(2, 2) 依赖于 Job(3, 2) 和 Job(3, 3)；对于任意 1 <= i < n, 1 <= j <= n，Job(i, j) 依赖于 Job(i + 1, j) 和 Job(i + 1, j + 1)。最后一行的任务没有任务依赖。
这批任务有一个特点，每个任务都需要配合它所依赖的任务来执行。也就是说，一个任务某次运行是有效的，当且仅当至少满足下列一个条件：
1. 该任务不依赖其它任务；
2. 该任务依赖的两个任务都是有效的。
每个任务都预先设定了一个权重 weight(i, j)。现在由于资源上的限制，我们只能挑选其中的 k 个任务来运行。我们希望所有被运行的任务都是有效的，并使得所有运行过的任务的权重之和最大。
输入格式
第一行是两个整数 n 和 k。
接下来 n 行，其中第 i 行 (1 <= i <= n) 包含 i 个整数，给出各个任务的权重。这个三角形也同时描述了任务的依赖关系。
输出格式
输出仅包含一个整数，即所求的最大权重和。
输入样例
3 4
1
2 3
1 1 1
输出样例
6
数据规模
对于 30% 的数据，1 <= n, k <= 50；
对于 100% 的数据，1 <= n <= 100，1 <= m <= C(n + 1, 2)，1 <= weight(i, j) <= 1000。
#include <bits/stdc++.h> const int N = 60; const int M = 500 + 10;//动态规划。把三角形翻转一下, 从底部到顶考虑每个元素。 //dp[i][j][k]表示考虑到第(i, j)个, 当前选取了k个元素的最大值。 //用前缀和维护一下最大值。 int dp[N][N][M], sum[N][N], a[N][N], n, m; int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= i; ++ j) { scanf("%d", &a[i][j]); } } for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= i; ++ j) { sum[i][j] = sum[i][j - 1] + a[n - j + 1][i - j + 1]; } } memset(dp, 200, sizeof(dp)); for(int i = 0; i <= n; ++ i) { dp[i][0][0] = 0; } for(int i = 1; i <= n; ++ i) { for(int j = i; j >= 0; -- j) { for(int k = j; k <= m; ++ k) { dp[i][j][k] = std::max(dp[i][j + 1][k], dp[i - 1][std::max(0, j - 1)][k - j] + sum[i][j]); } } } printf("%d\n", dp[n][0][m]); return 0; }