一次AC。
考慮當(dāng)m>2時(shí)，當(dāng)大頭吃掉k個(gè)果子之后，小頭只需要交叉著去吃就絕對不會(huì)有“難受值”；m==2時(shí)的情況需要考慮到。此時(shí)問題轉(zhuǎn)化為求大頭吃掉k個(gè)果子的最小難受值，具體做法為動(dòng)態(tài)規(guī)劃。
《算法藝術(shù)與信息學(xué)競賽》上出了點(diǎn)錯(cuò)。
將樹用“左兒子右兄弟”表示法表示。類似“重建道路”，考慮定義f[i][j]表示以i為根的樹上，取j個(gè)果子的最小難受值，但是這樣的話難受值無法計(jì)算出來，所以再加一維：定義f[i][j][k]表示以i為根的樹上，取j個(gè)果子的最小難受值，k==1表示i的父親被大頭吃，k==0表示i的父親被小頭吃。
所以有以下狀態(tài)轉(zhuǎn)移方程：
x1=tree[i].l；x2=tree[i].r；
f[i][j][k]=min{ f[x1][jj][1]+f[x2][j-jj-1][k]+d(1,k)*w[father[i]][i]，// (*1)
f[x1][jj][0]+f[x2][j-jj][k]+d(0,k)*w[father[i]][i] }；// (*2)
其中d(i,j)=1,(i==1&&j==1)||(i==0&&j==0&&m==2)；else d(i,j)=0;
(*2)可以決策的條件是i不是根結(jié)點(diǎn)，因?yàn)楦Y(jié)點(diǎn)必被大頭吃掉。
狀態(tài)轉(zhuǎn)移方程中jj的取值容易推出，要考慮幾種情況，不再細(xì)述。
在進(jìn)行treedp之前，要先計(jì)算出以各個(gè)結(jié)點(diǎn)為根的樹的結(jié)點(diǎn)數(shù)目。
以下是我的代碼：
#include<stdio.h>
#define maxv 301
#define maxint 200000000
typedef struct NODE
{
long x,l,r;
}node;
long m,n,k,root,father[maxv]={0},w[maxv][maxv]={0};
long f[maxv][maxv][2],num[maxv]={0},ans;
node tree[maxv];
void ins(long fa,long son)
{
long p;
if(tree[fa].l==0)
tree[fa].l=son;
else
{
p=tree[fa].l;
while(tree[p].r!=0)
p=tree[p].r;
tree[p].r=son;
}
}
void count(long node)
{
long x1,x2;
if(node==0) return;
num[node]=1;
x1=tree[node].l;
count(x1);
num[node]+=num[x1];
x2=tree[node].r;
count(x2);
num[node]+=num[x2];
}
void init()
{
long i,j,fa,son,weight;
scanf("%ld%ld%ld",&n,&m,&k);// N個(gè)頂點(diǎn) M個(gè)頭 吃掉K個(gè)
for(i=1;i<=n;i++)
{
tree[i].x=i;
tree[i].l=tree[i].r=0;
}
for(i=1;i<=n-1;i++)
{
scanf("%ld%ld%ld",&fa,&son,&weight);
ins(fa,son);
father[son]=fa;
w[fa][son]=weight;
}// Build a Tree
// Read In
for(i=1;i<=n;i++)
if(father[i]==0)
{root=i;break;}// Find the Root
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
f[i][j][0]=-1;
f[i][j][1]=-1;
}
count(root);
}
long d(long i,long j)
{
if((i==0&&j==0&&m==2)||(i==1&&j==1)) return 1;
return 0;
}
long dp(long node,long nn,long kk)
{
if(f[node][nn][kk]!=-1)
return f[node][nn][kk];
if(node==0) return 0;
long i,x1,x2,t;
f[node][nn][kk]=maxint;
x1=tree[node].l;
x2=tree[node].r;
for(i=0;i<=num[x1];i++)
{
if(i>=nn-num[x2]-1&&i<=nn-1)
{
t=dp(x1,i,1)+dp(x2,nn-i-1,kk)+d(1,kk)*w[father[node]][node];
if(t<f[node][nn][kk]) f[node][nn][kk]=t;
}
if(i>=nn-num[x2]&&i<=nn&&node!=root)// 只有此結(jié)點(diǎn)不是根節(jié)點(diǎn)才有可能不被大頭吃掉
{
t=dp(x1,i,0)+dp(x2,nn-i,kk)+d(0,kk)*w[father[node]][node];
if(t<f[node][nn][kk]) f[node][nn][kk]=t;
}
}
return f[node][nn][kk];
}
void write()
{
printf("%ld\n",ans);
}
int main()
{
init();
if(n>=k+m-1)
ans=dp(root,k,0);
else ans=-1;
write();
return 0;
}