Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## AC 疏星背包的时候要从后往前更新，否则一个点会被一个儿子更新两遍

Posted by PoPoQQQ at 2014-04-24 18:19:22 on Problem 2486
```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define s son[x][i]
int max(int x,int y){return x>y?x:y;}
int f[110][210][2];//f[i][j][0]=x表示从i点开始走j步回到i点能吃到最多苹果，1是不回来；
int a[110],fa[110],son[110][110],mark[110];
int ans;
int n,k;
void build_tree(int x)
{
abcd*temp;
mark[x]=1;
}
void Treedp(int x)
{
int i,j,l;
f[x][0][0]=a[x];
for(i=1;s;i++)
{
Treedp(s);
for(j=k;j>=0;j--)for(l=k;l>=0;l--)
{
if(j+l>=k)continue;
f[x][j+l+1][1]=max(f[x][j+l+1][1],f[x][j][0]+f[s][l][1]);
if(j+l+2>k)continue;
f[x][j+l+2][0]=max(f[x][j+l+2][0],f[x][j][0]+f[s][l][0]);
f[x][j+l+2][1]=max(f[x][j+l+2][1],f[x][j][1]+f[s][l][0]);
}
}
f[x][0][1]=a[x];
}
int main()
{
int i,j,x,y;
while(scanf("%d",&n)!=EOF)
{
memset(f,0xef,sizeof(f));
memset(son,0,sizeof(son));
memset(mark,0,sizeof(mark));
ans=0;
scanf("%d",&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
build_tree(1);
Treedp(1);
for(i=0;i<=k;i++)ans=max(ans,max(f[1][i][0],f[1][i][1]));
printf("%d\n",ans);
}
}

C的代码，略原始，凑活看吧```

Followed by: