[IOI2005]Riv河流

题目链接：洛谷，BZOJ
前置知识：莫得

题解

直接考虑dp。首先想法是设状态 \(dp[u][i]\) 表示u的子树内建 \(i\) 个伐木场且子树内木头都运到某个伐木场的最小花费。发现这样的状态是无法从儿子转移到父亲的，考虑加一维状态。
可以发现题目中有一个条件是 木头会在运输过程中第一个碰到的新伐木场被处理 。那么可以加一维状态 \(k\) 表示离 \(u\) 最近的一个建有伐木场的祖先为 \(k\) ，可以发现这样就可以转移了。
注意一些转移时的细节，比如说 \(0\) 号节点初始就建有伐木场。

#include<bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define rep(i, s, t) for(int i = s, __ = t; i <= __; ++i)

#define dwn(i, s, t) for(int i = s, __ = t; i >= __; --i)

const int INF = 2147483647;

const int MAXN = 100 + 100;

const int MOD = 998244353;

using namespace std;

inline int read(int x = 0, int f = 1){

    char ch = getchar();

    for(; !isdigit(ch); ch = getchar())if(ch == '-')f = -1;

    for(; isdigit(ch); ch = getchar())x = ch - '0' + x * 10;

    return x * f;

}

inline void write(int x){

    if(x < 0)x = -x, putchar('-');

    if(x >= 10)write(x / 10); putchar(x % 10 + '0');

    return ;

}

int n, k, w[MAXN], num = -1, fs[MAXN]; struct List{int nt, to, w;}Edge[MAXN];

#define ten(cur, u) for(int cur = fs[u]; cur != -1; cur = Edge[cur].nt)

inline void AddEdge(int x, int y, int w){

	Edge[++num].nt = fs[x], fs[x] = num, Edge[num].to = y, Edge[num].w = w;

	return ;

}

int sup[MAXN][MAXN], fa[MAXN],vis[MAXN];

int dp[MAXN][MAXN][MAXN], dis[MAXN];

inline void upd(int &x, int y){

	if(y == -1)return ; x = x == -1 ? y : min(x, y); return ;

}

void dfs(int u, int dep){

	dis[u] = dep, vis[u] = 1, dp[u][u][u != 0] = 0;

	rep(i, 0, n)if(vis[i] && i != u)dp[u][i][0] = w[u] * (dis[u] - dis[i]);

	rep(i, 0, n)rep(j, 0, k)sup[i][j] = -1;

	ten(cur, u){

		int v = Edge[cur].to; dfs(v, dep + Edge[cur].w);

		rep(i, 0, n){

			if(!vis[i])continue;

			rep(j, 0, k){

				rep(p, 0, k){

					if(j + p > k)break;

					if((dp[v][i][j] != -1) && (dp[u][i][p] != -1))

						upd(sup[i][j + p], dp[v][i][j] + dp[u][i][p]);

					if((j + p <= k) && (dp[v][v][j] != -1) && (dp[u][i][p] != -1))

						upd(sup[i][j + p], dp[v][v][j] + dp[u][i][p]);

				}

			}

		}

		rep(i, 0, n)rep(j, 0, k)dp[u][i][j] = sup[i][j], sup[i][j] = -1;

	}

	vis[u] = 0; return ;

}

int main(){

	memset(fs, -1, sizeof(fs)); memset(dp, -1, sizeof(dp));

	n = read(), k = read();

	rep(i, 1, n)w[i] = read(), fa[i] = read(), AddEdge(fa[i], i, read());

	dfs(0, 0); write(dp[0][0][k]); return 0;

}

巴特西

[IOI2005]Riv河流

题解

最新文章

热门文章