P3354 河流
xuyiyan920 · · 个人记录
-
这题是一道树形dp题。因为必须要知道到伐木场的距离才可以求出花费,进行转移,所以这题的dp状态在原有的
dp[i][j] (i 为当前结点,j 为已选伐木场)上加一维,dp[i][j][k] 为最小花费,j 表示在i 下游最近的伐木场。这样可以通过dp实现。```cpp dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j],dp[now][0][s[m]][j-l]+dp[to][0][s[m]][l]); dp[now][1][s[m]][j]=min(dp[now][1][s[m]][j],dp[now][1][s[m]][j-l]+dp[to][0][now][l]); ``` -
这题dp初值应为0,然而这会影响第一轮的转移(不会被更新),所以应将
dp[now][0][s[m]][j]+=dp[to][0][s[m]][0]; dp[now][1][s[m]][j]+=dp[to][0][now][0];提至
l 的循环转移外,可以使第一轮转移正确。 -
在处理完当前结点后,应当对[0],[1]进行合并,因为这对下一步转移并没有影响,有影响的只是
j 。if(j>=1) dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j]+w[now]*(dis[now]-dis[s[m]]),dp[now][1][s[m]][j-1]); else dp[now][0][s[m]][0]+=w[now]*(dis[now]-dis[s[m]]); -
还有注意
[1] 在之前转移时并没有算上当前i的伐木场,所以在这里需要从[j-1]转移过来,并对j进行特判,以免越界。 -
最后取
dp[0][0][0][k] 。#include <bits/stdc++.h> using namespace std; const int MAXN=100+10; struct node { int v,ne,w; }; node t[MAXN<<1]; int n,k,head[MAXN],w[MAXN],cnt,l,dp[MAXN][2][MAXN][MAXN],s[MAXN],hea,dis[MAXN]; void build(int u,int v,int w) { t[++cnt].v=v,t[cnt].w=w; t[cnt].ne=head[u],head[u]=cnt; } void dfs(int now,int fa) { s[hea++]=now; for(int i=head[now];i;i=t[i].ne) { int to=t[i].v; if(to==fa) continue; dis[to]=dis[now]+t[i].w; dfs(to,now); } for(int i=head[now];i;i=t[i].ne) { int to=t[i].v; if(to==fa) continue; for(int m=0;m<hea;m++) { for(int j=k;j>=0;j--) { dp[now][0][s[m]][j]+=dp[to][0][s[m]][0]; dp[now][1][s[m]][j]+=dp[to][0][now][0]; for(int l=0;l<=j;l++) { dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j],dp[now][0][s[m]][j-l]+dp[to][0][s[m]][l]); dp[now][1][s[m]][j]=min(dp[now][1][s[m]][j],dp[now][1][s[m]][j-l]+dp[to][0][now][l]); } } } } for(int m=0;m<hea;m++) { for(int j=k;j>=0;j--) { if(j>=1) dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j]+w[now]*(dis[now]-dis[s[m]]),dp[now][1][s[m]][j-1]); else dp[now][0][s[m]][0]+=w[now]*(dis[now]-dis[s[m]]); } } hea--; } int main() { cin>>n>>k; for(int i=1;i<=n;i++) { int vi,di; cin>>w[i]>>vi>>di; build(i,vi,di); build(vi,i,di); } dfs(0,-1); cout<<dp[0][0][0][k]<<endl; return 0; }