我的题解+代码

105是10^5
May The Father Of Understanding Guide U

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

int N,M,K;

struct Edge
{
int to,next;
int weight;
void assign(int t,int n,int w)
{
to=t; next=n; weight=w;
}
};

Edge elist[605];
int head[305];
bool vis[305];
int child[305][2]; //0 is left and 1 is right
int weight[305];
int ecnt;

void initE()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(child,-1,sizeof(child));
weight[1]=0;
ecnt=0;
}

inline void addEdge(int from,int to,int weight)
{
elist[ecnt].assign(to,head[from],weight);
head[from]=ecnt++;
elist[ecnt].assign(from,head[to],weight);
head[to]=ecnt++;
}

bool input()
{
scanf("%d%d%d",&N,&M,&K);
bool ok=true;
if(K+M-1>N) ok=false;
initE();
int a,b,c;
for(int i=1;i<N;i++)
{
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
}
return ok;
}

void buildBinaryTree(int cur)
{
vis[cur]=true;
int last=-1;
for(int e=head[cur];e!=-1;e=elist[e].next)
{
int& to=elist[e].to;
int& w=elist[e].weight;
if(!vis[to])
{
weight[to]=w;
if(last==-1)
child[cur][0]=to;
else
child[last][1]=to;
last=to;
buildBinaryTree(to);
}
}
}

int dp[305][305][2];

std::queue<int> seq;

void getSeq(int cur)
{
if(child[cur][1]!=-1) getSeq(child[cur][1]);
if(child[cur][0]!=-1) getSeq(child[cur][0]);
seq.push(cur);
}

int solve_aux_3()
{
int ans;
while(!seq.empty())
{
int cur=seq.front();
seq.pop();
int st(0);
if(child[cur][1]!=-1) st|=1;
if(child[cur][0]!=-1) st|=2;
if(st==0)
{
dp[cur][0][0]=dp[cur][0][1]=0;
dp[cur][1][0]=0;
dp[cur][1][1]=weight[cur];
}
else if(st==1)
{
int& rc=child[cur][1];
dp[cur][0][0]=0;
for(int i=1;i<K;i++)
dp[cur][i][0]=std::min(dp[rc][i][0],dp[rc][i-1][0]);
dp[cur][0][1]=0;
for(int i=1;i<K;i++)
dp[cur][i][1]=std::min(dp[rc][i][1],dp[rc][i-1][1]+weight[cur]);
}
else if(st==2)
{
int& lc=child[cur][0];
if(cur==1) ans=dp[lc][K-1][1];
else
{
dp[cur][0][0]=dp[cur][0][1]=0;
for(int i=1;i<K;i++)
dp[cur][i][0]=std::min(dp[lc][i][0],dp[lc][i-1][1]);
for(int i=1;i<K;i++)
dp[cur][i][1]=std::min(dp[lc][i][0],dp[lc][i-1][1]+weight[cur]);
}
}
else //st=3
{
int& lc=child[cur][0];
int& rc=child[cur][1];
dp[cur][0][0]=dp[cur][0][1]=0;
for(int i=1;i<K;i++)
{
for(int j=0;j<=i;j++)
dp[cur][i][0]=std::min(dp[lc][j][0]+dp[rc][i-j][0],dp[cur][i][0]);
for(int j=0;j<i;j++)
dp[cur][i][0]=std::min(dp[lc][j][1]+dp[rc][i-j-1][0],dp[cur][i][0]);
}
for(int i=1;i<K;i++)
{
for(int j=0;j<=i;j++)
dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][0]+dp[rc][i-j][1]);
for(int j=0;j<i;j++)
dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][1]+dp[rc][i-j-1][1]+weight[cur]);
}
}
}
return ans;
}

int solve_aux_2()
{
int ans;
while(!seq.empty())
{
int cur=seq.front();
seq.pop();
int st(0);
if(child[cur][1]!=-1) st|=1;
if(child[cur][0]!=-1) st|=2;
if(st==0)
{
dp[cur][0][1]=dp[cur][1][0]=0;
dp[cur][0][0]=dp[cur][1][1]=weight[cur];
}
else if(st==1)
{
int& rc=child[cur][1];
dp[cur][0][1]=dp[rc][0][1];
dp[cur][0][0]=dp[rc][0][0]+weight[cur];
for(int i=1;i<K;i++)
{
dp[cur][i][0]=std::min(dp[rc][i][0]+weight[cur],dp[rc][i-1][0]);
dp[cur][i][1]=std::min(dp[rc][i][1],dp[rc][i-1][1]+weight[cur]);
}
}
else if(st==2)
{
int& lc=child[cur][0];
if(cur==1) ans=dp[lc][K-1][1];
else
{
dp[cur][0][1]=dp[lc][0][0];
dp[cur][0][0]=dp[lc][0][0]+weight[cur];
for(int i=1;i<K;i++)
{
dp[cur][i][0]=std::min(dp[lc][i][0]+weight[cur],dp[lc][i-1][1]);
dp[cur][i][1]=std::min(dp[lc][i][0],dp[lc][i-1][1]+weight[cur]);
}
}
}
else
{
int& lc=child[cur][0];
int& rc=child[cur][1];
dp[cur][0][1]=dp[lc][0][0]+dp[rc][0][1];
dp[cur][0][0]=dp[lc][0][0]+dp[rc][0][0]+weight[cur];
for(int i=1;i<K;i++)
{
for(int j=0;j<=i;j++)
dp[cur][i][0]=std::min(dp[cur][i][0],dp[lc][j][0]+dp[rc][i-j][0]+weight[cur]);
for(int j=0;j<i;j++)
dp[cur][i][0]=std::min(dp[cur][i][0],dp[lc][j][1]+dp[rc][i-j-1][0]);
for(int j=0;j<=i;j++)
dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][0]+dp[rc][i-j][1]);
for(int j=0;j<i;j++)
dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][1]+dp[rc][i-j-1][1]+weight[cur]);
}
}
}
return ans;
}

int solve()
{
memset(dp,0x3f,sizeof(dp));
buildBinaryTree(1);
getSeq(1);
return M==2?solve_aux_2():solve_aux_3();
}

int main()
{
if(!input()) printf("-1");
else printf("%d",solve());
return 0;
}
为啥你萌都说这题很水(´･ω･｀)

又A了一道水题，谁能告诉我vijos上的Win版MC怎么打开啊啊啊！！！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int point[303],next[603],v[603],c[603],cnt=0,N,M,K,f[303][303][2],d[303],con[303],pre[303];
int l[303],r[303];
bool p[303];
void insect(int x,int y,int z){next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;cnt++;}
void dfs(int x)
{
int i,j=-1;
for (i=point[x];i!=-1;i=next[i])
if (p[v[i]]==0)
{
p[v[i]]=1;
if (l[x]==0) l[x]=v[i],d[v[i]]=c[i],pre[v[i]]=0,j=l[x]; else
{
r[j]=v[i]; d[v[i]]=c[i]; pre[r[j]]=j; j=r[j];
}
}
if (j==-1) return;
dfs(j); con[j]=con[l[j]]+1;
while (pre[j]!=0) j=pre[j],dfs(j),con[j]=con[l[j]]+con[r[j]]+1;
}
int dp(int x,int k,int t)
{
if (x==0) return 0;
if (f[x][k][t]!=-1) return f[x][k][t];
int i,l1,r1,num=1000000000;
for (i=0;i<k;++i)
if ((i<=con[l[x]])&&(k-1-i<=con[r[x]]))
{
l1=dp(l[x],i,1);
r1=dp(r[x],k-1-i,t);
num=min(num,l1+r1+(t==1)*d[x]);
}
for (i=0;i<=k;++i)
if ((i<=con[l[x]])&&(k-i<=con[r[x]]))
{
l1=dp(l[x],i,0);
r1=dp(r[x],k-i,t);
num=min(num,l1+r1+(M==2)*(t==0)*d[x]);
}f[x][k][t]=num;
return num;
}
int main()
{
memset(point,-1,sizeof(point));
memset(next,-1,sizeof(next));
memset(f,-1,sizeof(f));
memset(v,0,sizeof(v));
memset(c,0,sizeof(c));
memset(p,0,sizeof(p));
scanf("%d %d %d\n",&N,&M,&K);
if (K+M-1>N) {printf("-1\n");return 0;}
int i,a,b,c;
for (i=1;i<N;++i)
{
scanf("%d %d %d\n",&a,&b,&c);
insect(a,b,c);insect(b,a,c);
}p[1]=1; dfs(1);
printf("%d\n",dp(l[1],K-1,1));
return 0;
}

树状DP 寻找根节点
#include<cstdio>

#include<iostream>

#include <algorithm>

#include <cstdlib>

#include<cstring>
using namespace std;
#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个顶点 M个头 吃掉K个
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;
}
for(i=1;i<=n;i++)
if(father[i]==0)
{
root=i;
break;
}
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)// 只有此结点不是根节点才有可能不被大头吃掉
{
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;
}

[blue]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 306ms

├ 测试数据 08：答案正确... 322ms

├ 测试数据 09：答案正确... 822ms

├ 测试数据 10：答案正确... 728ms

多叉树转二叉树

[red]

树型dp

f表示i为跟的子树

d=1 表示大头吃掉fa[i]

d=0 表示小头吃掉fa[i]

大头吃掉以i为跟的子树

k个果子的最小代价，

方程就很简单了

f:=min(f[left[i],1,j]+f[right[i],d,k-j-1]+dist[fa[i],i]*b[d,1] ( 0

被我用多叉树硬A掉了！

黑书p142-143，讲的很清楚了，自己看看吧。

提醒一下，一开始写了一个记忆化搜索，后面的基本全超时，建议不要写。

注意几点

1.过程调用不是一般的慢,最好还是用函数调用

2.不要默认边>0

3.转二叉程序更简洁,思路更明确

4.有个小小的儿子树优化

就是当分给大头的果子数NEED>SON[now]时,无需计算,直接返回oo

我知道方程,怎么会超时的呢

function f(i,j,k:longint):longint;

var j1,x1,x2:longint;

begin

if j>sum[i] then exit(oo);

if dp>0 then exit(dp);

if (i=0)and(j=0) then exit(0);

x1:=tree[i].l;x2:=tree[i].r;

dp:=oo;

for j1:=0 to min(j-1,sum[x1]) do

dp:=min(f(x1,j1,0)+f(x2,j-j1-1,k)+d(k,0)*cost,dp);

for j1:=0 to min(j,sum[x1]) do

dp:=min(f(x1,j1,1)+f(x2,j-j1,k)+d(k,1)*cost,dp);

f:=dp;

end;

大牛罩我

又是1A好难过

树形动规，说是转二叉但是感觉没什么区别。。。

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

九头龙吃了我的期中考试...

Accepted 有效得分：100 有效耗时：0ms

诧异了...d[0,0]和d[1,1]打反了.....

参考了《算法艺术与信息学竞赛》的题解，可是惊奇的发现书上居然写错了.......

终于AC了

本人第一道多叉转2叉

高兴ING

编了30分钟100行，本以为可以了，但是...

查错查了一个晚上

8个点到10个点就那么难吗~~

人世间最难过的莫过于此~~~

多叉树型也好理解！！！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

细节问题 太痛苦了

总算AC了 。。。囧了好久

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

记忆化搜索....

答案输出应该是 f(lchild[1],k-1,1) 调试了一个晚上都没发现

方程见 算法艺术

Orz大牛们！