[LGOJ1273]有线电视网

solution

用了一个很有意思的转移方法。

$dp[i][j] $ 表达 $i$ 作为根，$j$个终端时最大的收益，即钱数，当$0\leq dp[1][i]$时，即以1为根可以转移到$i$个终端，且不亏本，此时$i$也最大时，i就是答案。

然后就是树上背包的套路题了。。

\[dp[u][j] = max(dp[u][j], dp[u][j - k]+dp[v][k]-len(u, v))
\]

自己思考一下。

code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3000 + 5;

int n, m, a[maxn], dp[maxn][maxn]; // id & zhongduan_num;

struct node {int to, z;};

vector <node> e[maxn];

int dfs(int x) {

	if(x > n - m) {

		dp[x][1] = a[x];

		return 1;

	}

	int sum = 0;

	for(int i = 0;i < e[x].size();i ++) {

		int y = e[x][i].to, z = e[x][i].z, son = dfs(y);

		sum += son;

		for(int v = sum; v >= 0; v --) {

			for(int j = 1;j <= min(son, v);j ++) {

				dp[x][v] = max(dp[x][v], dp[x][v - j] + dp[y][j] - z);

			}

		}

	}

	return sum;

}

int main() {

	memset(dp, 0xcf, sizeof(dp));

	cin >> n >> m;

	for(int i = 1;i <= n;i ++)

		dp[i][0] = 0;

	for(int i = 1, A, C;i <= n - m;i ++) {

		int k; cin >> k;

		for(int j = 1;j <= k;j ++) {

			cin >> A >> C;

			e[i].push_back((node){A, C});

		}

	}

	for(int i = 1;i <= m;i ++) {

		cin >> a[n - m + i];

	}

	dfs(1);

	for(int i = m;i >= 1;i --) {

		if(dp[1][i] >= 0) {

			cout << i;

			return 0;

		}

	}

	puts("0");

	return 0;

}

巴特西

[LGOJ1273]有线电视网

solution

code

thanks

最新文章

热门文章