来一发

#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x7f7f7f7f
using namespace std;
struct node{
int left,right,num,dis;
}gg[105];
int dui[105],deep[105],child[105],f[105][105][51],tot,fa[105];
void dfs(int k,int dep)
{
dui[++tot]=k;
deep[k]=dep+gg[k].dis;
int i=gg[k].left;
while(i)
{
dfs(i,deep[k]);
i=gg[i].right;
}
}
int main()
{
int n,K;
cin>>n>>K;
memset(fa,-1,sizeof fa);
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(!child[b])
gg[b].left=i;
else
gg[child[b]].right=i;
child[b]=i;
gg[i].num=a;
gg[i].dis=c;
fa[i]=b;
}
dfs(0,0);
int llll;
memset(f,INF,sizeof f);
memset(f[0],0,sizeof f[0]);
for(int i=n+1;i>=2;i--)
{
int now=dui[i];
int le=gg[now].left;
int ri=gg[now].right;
for(int j=fa[now];j!=-1;j=fa[j])
for(int k=0;k<=K;k++)
{
for(int l=0;l<=k;l++)
if(f[le][j][l]!=INF&&f[ri][j][k-l]!=INF)
{
int add=gg[now].num*(deep[now]-deep[j]);
int op=f[le][j][l]+f[ri][j][k-l]+add;
f[now][j][k]=min(f[now][j][k],op);
}
for(int l=0;l<k;l++)
if(f[le][now][l]!=INF&&f[ri][j][k-l-1]!=INF)
{
int op=f[le][now][l]+f[ri][j][k-l-1];
f[now][j][k]=min(op,f[now][j][k]);
}
}
}
printf("%d",f[gg[0].left][0][K]);
}


我的AC率啊，为何每第一次交都*CE*？
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool p[103];
int N,K,point[103],next[203],v[203],c[203],w[103],cnt=0;
int f[103][103][103],l[103],r[103],dist[103];
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;
for (i=point[x];i!=-1;i=next[i])
if (p[v[i]]==0)
{
if (l[x]==0) l[x]=v[i],dist[v[i]]=dist[x]+c[i]; else
{
j=l[x];
while (r[j]!=0) j=r[j];
r[j]=v[i]; dist[v[i]]=dist[x]+c[i];
}p[v[i]]=1;
}
i=l[x]; while (i!=0){dfs(i);i=r[i];}
}
int dp(int x,int fa,int k)
{
if (x==0) return 0;
if (f[x][fa][k]!=-1) return f[x][fa][k];
if (k==0) {
int now=(dist[x]-dist[fa])*w[x];
if (l[x]!=0) now+=dp(l[x],fa,k);
if (r[x]!=0) now+=dp(r[x],fa,k);
f[x][fa][k]=now; return now;
}
int i;f[x][fa][k]=2000000001;
for (i=0;i<=k;++i)
f[x][fa][k]=min(f[x][fa][k],dp(l[x],fa,i)+dp(r[x],fa,k-i)+w[x]*(dist[x]-dist[fa]));
for (i=0;i<k;++i)
f[x][fa][k]=min(f[x][fa][k],dp(l[x],x,i)+dp(r[x],fa,k-1-i));
return f[x][fa][k];
}
int main()
{
memset(point,-1,sizeof(point));
memset(next,-1,sizeof(next));
memset(dist,0,sizeof(dist));
memset(v,-1,sizeof(v));
memset(f,-1,sizeof(f));
memset(c,0,sizeof(c));
memset(w,0,sizeof(w));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(p,0,sizeof(p));
scanf("%d %d\n",&N,&K);
int i,di,vi;
for (i=1;i<=N;++i)
{
scanf("%d %d %d\n",&w[i],&vi,&di);
insect(i,vi,di);insect(vi,i,di);
}p[0]=1;dfs(0);
printf("%d\n",dp(l[0],0,K));
return 0;
}

树形DP 记忆化搜索

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define sz 110
#define LL long long
#define for1(v,a,b) for (int v=a;v<=b;v++)
#define for2(v,a,b) for (int v=a;v>=b;v--)
using namespace std;
int left[sz],right[sz];
int w[sz],d[sz],f[sz][sz][sz];
int n,k,p;
int DP(int from,int to,int k,int s){
if ((from==n+1)||(to==n+1)) return 0;
if (f[from][to][k]!=-1) return f[from][to][k];
int x=2000000010;
for1(i,0,k-1) //都怪你
x=min(x,DP(left[from],from,i,0)+DP(right[from],to,k-i-1,s));
for1(i,0,k)
x=min(x,DP(left[from],to,i,s+d[from])+DP(right[from],to,k-i,s)+(s+d[from])*w[from]);
f[from][to][k]=x;
return x;
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d%d",&n,&k);
for1(i,0,n){
left[i]=n+1;
right[i]=n+1;
for1(j,0,n)
for1(p,0,k)
f[i][j][p]=-1;
}
for1(i,1,n){
scanf("%d%d%d",&w[i],&p,&d[i]);
right[i]=left[p];
left[p]=i;
}
printf("%d",DP(left[0],0,k,0));
return 0;
}

这个输入文件不对吧，我的AC率啊！

又 A 一遍 膜拜 嘉林God Orz +1
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define INF 99999999
long long l[111],r[111],dis[111][111],w[111],f[111][111][111];
int n,m;
int max(int ax,int by){
return ax>by ? ax : by;
}
int min(int ax,int by){
return ax>by ? by : ax;
}
void insert(int k,int F){
if(!l[F]){l[F]=k;return;}
F=l[F];
while(r[F]) F=r[F];
r[F] = k;
}
int Dp(int now,int F,int k){
if(!now) return 0;
if(f[now][F][k]!=-1) return f[now][F][k];
int M=w[now]*dis[now][F];
if(!k) return f[now][F][k]=Dp(l[now],F,0)+Dp(r[now],F,0)+ M ;
if(!l[now]&&!r[now]) return 0;
f[now][F][k]=INF;
for(int i=0;i<=k;i++) f[now][F][k]=min(f[now][F][k],M+Dp(l[now],F,k-i)+Dp(r[now],F,i));
for(int i=0;i<k ;i++) f[now][F][k]=min(f[now][F][k],Dp(l[now],now,k-i-1)+Dp(r[now],F,i));
return f[now][F][k];
}
int main(){
// freopen("xx.in","r",stdin);
//freopen("xx.out","w",stdout);
scanf("%d%d",&n,&m);
memset(dis,1,sizeof(dis));
for(int i=1;i<=n;i++) dis[i][i]=0;
for(int i=1;i<=n;i++){
int u,L;
scanf("%d%d%d",&w[i],&u,&L);
dis[u][i]=dis[i][u]=L;
insert(i,u);
}
for(int k=0;k<=n;k++)
for(int j=0;j<=n;j++)
for(int i=0;i<=n;i++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
/* for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) printf("%d ",dis[i][j]);
printf("\n");
}*/
memset(f,-1,sizeof(f));
printf("%d",Dp(l[0],0,m));
}

AC +1 以下代码 题解见LS。。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
long long left[111],right[111],d[111][111],w[111],a, f[111][111][111];
int n,m,v,di,wi;

void find (int k,int root)
{
if(right[root]==0){
right[root]=k;
return ;
}
root=right[root];
while(left[root]!=0) root=left[root];
left[root]=k;
}
int min(int a,int b,int c)
{
int ans=a;
if(b<ans) ans=b;
if(c<ans) ans=c;
return ans;
}

void work()
{
for(int i=0;i<=n;i++) d[i][i]=0;
for(int k=0;k<=n;k++)
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];

}
int Dp(int now,int num,int root)
{
if(now==0) return 0;

if(f[now][num][root]>=0) return f[now][num][root];
int money=w[now]*d[now][root];
if(num==0)
{
f[now][num][root]=Dp(left[now],0,root)+Dp(right[now],0,root)+money;
return f[now][num][root];
}

if(left[now]==0&&right[now]==0)
{
f[now][num][root]=0;
return 0;

}
f[now][num][root]=Dp(right[now],num,root)+Dp(left[now],0,root)+money;
for(int k=0;k<num;k++)
f[now][num][root]=min(Dp(right[now],k,root)+Dp(left[now],num-k,root)+money,Dp(right[now],k,now)+Dp(left[now],num-k-1,root),f[now][num][root]);
return f[now][num][root];
}
int main()
{
//freopen("xx.in","r",stdin);
// freopen("xx.out","w",stdout);
scanf("%d%d",&n,&m);
memset(d,1,sizeof(d));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&w[i],&v,&a);
d[i][v]=d[v][i]=a;
find(i,v);

}
work();

memset(f,-1,sizeof(f));
printf("%d",Dp(right[0],m,0));
}

O(N^3) 的状态 ， O(N) 的 转移， 居然 也能 秒杀。。。

请问这题怎么优化可以秒杀第21个测试点？

多叉转两叉，得益于贪吃的九头蛇，好题，一年前我还没做出啊

[让人囧的记录，95分也算AC了囧囧]

自己的方法：多叉树转二叉树再进行记忆化搜索。写起来十分方便

多叉转二叉的作用：对于每个根root，根的左孩子left[root]是根的真正孩子，而根的右孩子right[root]是根的兄弟

详见M67的博文。

这样一来转移方程就很好写了

f表示以i为根的子树分配j个伐木场离i最近的一个下流的伐木场在k。

f:=

MAX{f[left[i],0..j,k]+f[right[i],j..0,k]}：是i这个点不放伐木场

MAX{f[left[i],0..j-1,i]+f[right[i],j-1..0,k]}：是i这个点设置伐木场

Orz此题 是个好题 值得一做

..exit写错位置了.. 超时N次........

还是多叉DP快啊！！sunny都秒杀^.^

只是细节太多

本沙茶的程序最后一个点巨慢……

int64居然挂了,longword居然ac

树型三维dp

算法：三维DP

数据结构：左孩子右兄弟

实现：记忆化搜索

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

难度三是因为n太小了

要是n在10000以上就有难度了

时间复杂度ms是n*k*k

背包咱想到了

三维也想到了

垃圾若死也打开了

一个声音高叫着

爬出来吧，给你标程

但我深知道

人的身躯，怎能从那数据线中爬出

唉，减肥去也

我们需要先把所有点对点的路径预处理好。

分两种情况，m枚举在儿子处造几个场

I位置不造场

F=min{f[son[i],m,k]+f[next[i],j-m,k]}+w

I位置造场，这时son[i]连到i

F=min{f[son[i],m,i]+f[next[i],j-m-1,k]}

把0当作跟会使编程方便。

3维,否则绝对后效.

我写的三维动态规划，如果不是像李永刚那么强的话，最好不要写O(n^2) 的算法，

李永刚大牛曾经给我讲过，可是没有听懂。