题目:https://www.luogu.org/problemnew/show/P3354

虽说是几个月前曾经讲过的题,但没有题解而自己(花了两个多小时)A了好高兴!!!

这是一个很好的套路:“承诺”以算值。

  伐木场放在哪里对于节点的值是有影响的,所以自然的思路就是把和该节点有关的伐木场位置也压进状态里,对于不同的状态算出不同的值;

    也就是“承诺”那些伐木场会放在哪里。

  相同的承诺之间才能转移。

这样就有了一个问题:该节点的“承诺”记录的是该节点上方的下一个伐木场在哪;但是该节点放不放伐木场对于转移也有影响。

  试图用“承诺下一个伐木场在0”表示该节点放伐木场,但是有诸多不对劲;比如根据定义,0处承诺了的话,上面就没有“下一个伐木场的位置”了,导致无法转移之类;

  然后终于想到可以再开一维状态0/1表示该节点到底放没放伐木场!这样一下就变得通顺又简单!

树形DP的坑点:那个 j 的倒序!仔细一看转移需要用到同层的小一些的 j 的。

        还有常规的看看siz等等。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=;const ll INF=0x7fffffff;
int n,m,head[N],fa[N],xnt,siz[N],len[N];
ll a[N],c[N][N],ed[N],dp[N][][N][];
struct Edge{
int next,to;ll w;
Edge(int n=,int t=,ll w=):next(n),to(t),w(w) {}
}edge[N<<];
void init(int cr,ll dis,int cnt,int nw)
{
c[cr][cnt]=dis*a[cr];if(cnt)dp[cr][][cnt][]=c[cr][cnt];
if(!nw)
{
len[cr]=cnt;return;
}
init(cr,dis+ed[nw],cnt+,fa[nw]);
}
void dfs(int cr)
{
siz[cr]=;for(int j=;j<=n;j++)dp[cr][j][][]=;
for(int k=;k<=len[cr];k++)dp[cr][][k][]=;
for(int i=head[cr],v;i;i=edge[i].next)
{
dfs(v=edge[i].to);
for(int j=min(m,siz[cr]+siz[v]);j>=;j--)//
{
for(int k=;k<=len[cr];k++)
{
dp[cr][j][k][]+=min(dp[v][][][],dp[v][][][]);
dp[cr][j][k][]+=min(dp[v][][k+][],dp[v][][k+][]);
// printf("dp[%d][%d][%d]=%lld dp[%d][%d][%d]=%lld\n"
// ,cr,j,k,dp[cr][j][k],v,0,k+1,dp[v][0][k+1]);
for(int l=max(,j-siz[cr]);l<=j&&l<=siz[v];l++)
dp[cr][j][k][]=min(dp[cr][j][k][],dp[cr][j-l][k][]+min(dp[v][l][k+][],dp[v][l][k+][])),
dp[cr][j][k][]=min(dp[cr][j][k][],dp[cr][j-l][k][]+min(dp[v][l][][],dp[v][l][][]));
// printf("dp[%d][%d][%d][0]=%lld dp[%d][%d][%d][0]=%lld\ndp[%d][%d][%d][0]=%lld dp[%d][%d][%d][1]=%lld\n"
// ,cr,j,k,dp[cr][j][k][0],cr,j-l,k,dp[cr][j-l][k][0],v,l,k+1,dp[v][l][k+1][0],v,l,k+1,dp[v][l][k+1][1]),
// printf("dp[%d][%d][%d][1]=%lld dp[%d][%d][%d][1]=%lld\ndp[%d][%d][%d][0]=%lld dp[%d][%d][%d][1]=%lld\n\n"
// ,cr,j,k,dp[cr][j][k][1],cr,j-l,k,dp[cr][j-l][k][1],v,l,k+1,dp[v][l][k+1][0],v,l,k+1,dp[v][l][k+1][1]);
}
}
siz[cr]+=siz[v];
}
}
int main()
{
scanf("%d%d",&n,&m);int x;ll z;
for(int i=;i<=n;i++)
{
scanf("%lld%d%lld",&a[i],&x,&z);
edge[++xnt]=Edge(head[x],i,z);head[x]=xnt;
fa[i]=x;ed[i]=z;
}
memset(dp,,sizeof dp);dp[][][][]=;
for(int i=;i<=n;i++)init(i,,,i);
dfs();
printf("%lld",dp[][m][][]);
return ;
}
05-26 13:27