本文共 1930 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到一种方法，使得有线电视网在不亏本的情况下尽可能多地向用户提供观看足球比赛的信号。我们可以使用树形动态规划来解决这个问题。
我们可以使用树形动态规划来解决这个问题。具体来说，对于每个节点，我们计算选择其子节点时的最大收益。我们定义f[i][j]表示在节点i选择j个子节点时的最大收益。最后，我们需要找到最大的k，使得f[1][k] >= 0，这样可以确保在不亏本的情况下尽可能多地向用户提供信号。
#include#include #include using namespace std;#define N (3000 + 100)#define res register intinline int read() { int x(0), f(1); char ch; while (!isdigit(ch = getchar())) { if (ch == '-') f = -1; while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); } return f * x;}int head[N], ver[N], nxt[N], edge[N];int f[N][N], n, m;void add(int x, int y, int z) { ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot; edge[tot] = z;}void dfs(int x) { if (x > n - m) return 1; int son = 0; for (res i = head[x]; i; i = nxt[i]) { int y = ver[i]; int tmp = dfs(y); son += tmp; for (res j = son; j > 0; j--) { for (res k = 1; k <= tmp; k++) { if (k <= j) { if (f[x][j] < f[x][j - k] + f[y][k] - edge[i]) { f[x][j] = f[x][j - k] + f[y][k] - edge[i]; } } } } } return son;}int main() { n = read(); m = read(); for (res x = 1; x <= n - m; x++) { int siz = read(); for (res i = 1; i <= siz; i++) { int y = read(), z = read(); add(x, y, z); } } memset(f, ~0x3f, sizeof(f)); for (res i = 1; i <= n; i++) f[i][0] = 0; for (res i = n - m + 1; i <= n; i++) f[i][1] = read(); tot = 0; dfs(1); for (res i = m; i >= 1; i--) { if (f[1][i] >= 0) return printf("%d\n", i), 0; } return 0;}
转载地址：http://idvfk.baihongyu.com/