//此题为没有上司的舞会的弱化版，有需要可以移步
//是比较简单的树状DP了
#include<iostream>
#include<vector>
using namespace std;
int dp[5010][2];
vector<int> q[5010];
void dfs(int u,int v)
{
    int d=q[u].size(),i;
    for(i=0;i<d;i++)
     {
        dfs(q[u][i],u);
        dp[u][0]+=max(dp[q[u][i]][0],dp[q[u][i]][1]);
        dp[u][1]+=dp[q[u][i]][0];
     }
    return ;
}
int main()
{
    int n,i,t;
    cin>>n;
    for(i=1;i<=n;i++)
     cin>>dp[i][1];
    for(i=2;i<=n;i++)
    {
        cin>>t;
        q[t].push_back(i);
    }
    dfs(1,1);
    cout<<max(dp[1][1],dp[1][0]);
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,f[5001][2];

struct node1
{
    int a,h,sn,s[5001];
}a[5001];

void dfs1(int x)
{
    int v1=0,v2=0;
    for (int i=1;i<=a[x].sn;i++)
    {
        dfs1(a[x].s[i]);
        v1+=max(f[a[x].s[i]][0],f[a[x].s[i]][1]);
        v2+=max(f[a[x].s[i]][0],0);
    }
    f[x][0]=max(f[x][0],v1);
    f[x][1]=max(f[x][1],a[x].a+v2);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        a[i].sn=0;
        memset(a[i].s,0,sizeof(a[i].s));
    }
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].a);
    a[0].h=a[1].h=0;
    a[0].s[++a[0].sn]=1;
    for (int i=2;i<=n;i++)
    {
        scanf("%d",&a[i].h);
        a[a[i].h].s[++a[a[i].h].sn]=i;
    }
    memset(f,0,sizeof(f));
    dfs1(0);
    printf("%d\n",f[0][0]);
}

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MAXN 6005
int v[MAXN];
int h[MAXN];
int f[MAXN][2];
vector <int> son[MAXN];//本题唯一STL
void DP(int x)
{
f[x][0]=0;//基本定义条件
f[x][1]=h[x];
for(int i=0;i<son[x].size();i++)//这里调用了vector库，STL大法好
{
int y=son[x][i];//STL就是方便
DP(y);//递归算法好
f[x][0]+=max(f[y][1],f[y][0]);//建立DP方程
f[x][1]+=f[y][0];//建立DP方程
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i];}
for(int i=2;i<=n;i++)
{
int y;
cin>>y;
son[y].push_back(i);//STL
v[i]=i;//其实这里完全没有必要
}

int root;
for(int i=1;i<=n;i++)
{
if(!v[i])//这个判断对应上面，其实完全可以去root=1，这样的话更灵活一些
{
root =i;
break;
}
}
DP(root);
cout<<max(f[root][0],f[root][1]);//输出最老的父亲的最大值
}

https://www.luogu.com.cn/problem/P1352

#include <bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m,root,x,y,f[N][2],a[N],head[N],cnt;
bool vis[N];
struct fy
{
    int t,next;
}edge[N];
void add(int x, int y)
{
    edge[++cnt].t=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int x,int fa)
{
    f[x][0]=0,f[x][1]=a[x];
    for(int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].t;
        if(y==fa) 
            continue;
        dfs(y,x);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }
}

signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
        scanf("%d",&x),add(x,i+1);
    dfs(1,0);
    printf("%d",max(f[1][0],f[1][1]));
    return 0;
} 

建树,dfs一次,转移是下标0不选,下标1选.转移方程如下.

#include<bits/stdc++.h>
int read(){int x=0,f=1;char c=getchar();for (;!isdigit(c);c=getchar()) f^=c=='-';for (;isdigit(c);c=getchar()) x=x*10+c-'0';return x*(f?1:-1);}
int write(int x){if (!x) return putchar(48);if (x<0) putchar('-'),x=-x;register int bit[20],p=0,i;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) putchar(bit[i]+48);}
using namespace std;
int n=read(),dp[6666][2],ans;
vector<int> lj[6666];

void dfs(int u)
{
for (int i:lj[u]) 
  {
  dfs(i);
  dp[u][1]+=dp[i][0];
  dp[u][0]+=max(dp[i][1],dp[i][0]);
  ans=max(ans,max(dp[u][0],dp[u][1]));
  }
}

int main()
{
int i;
for (i=1;i<=n;++i) dp[i][1]=read();
ans=dp[1][1];
for (i=2;i<=n;++i) 
  {
  int k=read();
  lj[k].push_back(i);
  }
dfs(1);
write(ans);
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5001;
inline int init(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
struct node{int lef,rig,val;}tree[maxn];
int n,fa[maxn],pos[maxn],ex[maxn][3000];
void readE(){
n=init();
for(int i=1;i<=n;i++)tree[i].val=init();
for(int i=1;i<n;i++)fa[i]=init();
for(int i=1;i<n;i++){
if(!pos[fa[i]])tree[fa[i]].lef=i+1;
else tree[pos[fa[i]]].rig=i+1;//儿子在左，兄弟在右
pos[fa[i]]=i+1;
}
}
int dpE(int r,int w){
if(ex[r][w])return ex[r][w];
int sum=0,pos;
if(w){//要自己，儿子不能来，兄弟可来可不来
pos=tree[r].lef;
while(pos)sum+=dpE(pos,0),pos=tree[pos].rig;
return ex[r][w]=sum+tree[r].val;
}
else {//不要自己，儿子可以来，兄弟也可以来
pos=tree[r].lef;
while(pos)sum+=max(dpE(pos,0),dpE(pos,1)),pos=tree[pos].rig;
return ex[r][w]=sum;
}
}
int main(){
readE();
printf("%d\n",max(dpE(1,0),dpE(1,1)));
return 0;
}
注释给的应该很清楚了，不懂的可以问，但我不一定会马上回

dfs

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, f[N], g[N], a[N], head[N], m;
struct edge {int to, next;} e[N];
void addedge (int u, int v) {e[++m] = (edge){v, head[u]}; head[u] = m;}
void dfs (int x) {
    for (int i = head[x]; i; i = e[i].next) {
        dfs (e[i].to);
        f[x] += max (g[e[i].to], 0);
        g[x] += max (f[e[i].to], g[e[i].to]);
    }
}
int main () {
    int fa; scanf ("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        scanf ("%d", &a[i]); f[i] = a[i];
    }
    for (int i = 2; i <= n; ++ i) {
        scanf ("%d", &fa); addedge (fa, i);
    } dfs (1); printf ("%d\n", max (f[1], g[1]));
    return 0;
}

bfs

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;

//----------------------------------------------------------------------

struct Queue {
    int seq[N], front, tail, size;
    void Clear () {
        memset (seq, 0, sizeof(seq));
        front = 1, tail = 0, size = 0;
    }
    void Push (int x) {
        if (tail == N) {seq[1] = x; tail = 1;}
        else seq[++ tail] = x;
        ++ size;
    }
    void Pop () {
        if (front == N) front = 1; else ++ front;
        -- size;
    }
    int Front () {return seq[front];}
    bool Empty () {return !size;}
};

//----------------------------------------------------------------------

int n, f[N], g[N], a[N], head[N], fa[N], m, rk[N], cnt;
struct edge {int to, next;} e[N];
Queue q;
void addedge (int u, int v) {
    e[++m] = (edge){v, head[u]}; head[u] = m;
}
void bfs (int x) {
    q.Clear(); q.Push(x);
    while (!q.Empty()) {
        for (int i = head[q.Front()]; i; i = e[i].next)
            q.Push(e[i].to);
        rk[++cnt] = q.Front(); q.Pop();
    }
}
int main () {
    int ff; scanf ("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        scanf ("%d", &a[i]); f[i] = a[i];
    }
    for (int i = 2; i <= n; ++ i) {
        scanf ("%d", &ff); addedge (ff, i);
        fa[i] = ff;
    } bfs (1);
    for (int i = n; i > 1; -- i) {
        int x = rk[i]; 
        f[fa[x]] += max (g[x], 0);
        g[fa[x]] += max (f[x], g[x]);
    }
    printf ("%d\n", max (f[1], g[1]));
    return 0;
}

其实这个顺序只要保证一个点的父亲在它的后面就行。。。

// 树形DP
{
f[i][0]:表示选第i个节点
f[i][1]:表示不选第i个节点

f[i][0]:=v[i]+sum(f[j][0]);
f[i][1]:=sum(max(f[j][0]+f[j][1]))
}
```
uses math;

type
re=record
v,next:longint;
end;

var
n,u,v,i,j,tot:longint;
a,last:array[0..5000]of longint;
f:array[0..5000,0..1]of longint;
t:array[0..5000*2]of re;

procedure add(u,v:longint);
begin
inc(tot);
t[tot].v:=v;
t[tot].next:=last[u];
last[u]:=tot;
end;

procedure Init;
var
i,j:longint;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
f[i][0]:=a[i];
end;
for i:=1 to n-1 do
begin
readln(u);
add(u,i+1); add(i+1,u);
end;
end;

procedure Dfs_Dp(i,fat:longint);
var
x,tox:longint;
begin
x:=last[i];
while x<>0 do
begin
tox:=t[x].v;
if tox<>fat then Dfs_Dp(tox,i);
x:=t[x].next;
end;
f[fat][0]:=f[fat][0]+f[i][1];
f[fat][1]:=f[fat][1]+max(f[i][1],f[i][0]);
end;

begin
Init;
Dfs_Dp(1,0);
writeln(max(f[1][0],f[1][1]));
end.
```

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int dp[5020][2];
int n;
int val[5020];
vector<int> node[5020];
void dfs(int fa){
dp[fa][0]=0;dp[fa][1]=val[fa];
for (int i=0;i<node[fa].size();i++){
int son=node[fa][i];
dfs(son);
dp[fa][1]+=dp[son][0];
dp[fa][0]+=max(dp[son][0],dp[son][1]);
}
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<n;i++){
int x;
scanf("%d\n",&x);
node[x].push_back(i+1);
}
dfs(1);
printf("%d\n",max(dp[1][0],dp[1][1]));
return 0;
}

P1706舞会
Accepted

记录信息

评测状态 Accepted
题目 P1706 舞会
递交时间 2015-08-25 23:03:19
代码语言 C++
评测机 VijosEx
消耗时间 115 ms
消耗内存 852 KiB
评测时间 2015-08-25 23:03:20

评测结果

编译成功

foo.cpp: In function 'int dp(int)':
foo.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < s[x] -> son.size() ; i++ )
^
foo.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < s[x] -> son.size() ; i++ )
^
foo.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( j = 0 ; j < s[ cur ] -> son.size() ; j++ )
^

测试数据 #0: Accepted, time = 0 ms, mem = 528 KiB, score = 10

测试数据 #1: Accepted, time = 1 ms, mem = 532 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 536 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 536 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 724 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 800 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 600 KiB, score = 10

测试数据 #7: Accepted, time = 34 ms, mem = 708 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 852 KiB, score = 10

测试数据 #9: Accepted, time = 20 ms, mem = 848 KiB, score = 10

Accepted, time = 115 ms, mem = 852 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

struct Node
{
vector < int > son;
int value;
int sonsum;
};

int n;
int i;
Node * s[5000 + 2];

int dp( int x )
{
if( s[x] -> son.size() == 0 )
return max( s[x] -> value , 0 );
if( s[x] -> sonsum != -1 )
return s[x] -> sonsum;
int i , j , cur;
for( i = 0 ; i < s[x] -> son.size() ; i++ )
s[x] -> sonsum += dp( s[x] -> son[i] );
s[x] -> sonsum++;
int temp = s[x] -> value;
for( i = 0 ; i < s[x] -> son.size() ; i++ )
{
cur = s[x] -> son[i];
for( j = 0 ; j < s[ cur ] -> son.size() ; j++ )
temp += dp( s[ cur ] -> son[j] );
}
s[x] -> sonsum = max( s[x] -> sonsum , temp );
return s[x] -> sonsum;
}

int root;
int t;

int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
{
s[i] = new Node();
s[i] -> sonsum = -1;
scanf( "%d" , &s[i] -> value );
}
for( i = 2 ; i <= n ; i++ )
{
scanf( "%d" , &t );
s[t] -> son.push_back( i );
}
root = 1;
cout << dp( root ) << endl;
return 0;
}

var
tot,i,j,k,n,m,s,t,ans:longint;
head,vet,next,a:array[0..5001]of longint;
f:array[0..5001,0..1]of longint;
p:array[0..5001]of boolean;
function max(i,j:longint):longint;
begin
if i>j then exit(i);exit(j);
end;
procedure add(u,v:longint);
begin
inc(tot);
vet[tot]:=v;
next[tot]:=head[u];
head[u]:=tot;
end;
procedure try(i:longint);
var j,t,e:longint;
begin
if p[i] then exit;
f[i,0]:=0;f[i,1]:=a[i];
e:=head[i];
while e<>-1 do
begin
j:=vet[e];
try(j);t:=max(f[j,0],f[j,1]);
if t<0 then t:=0;
f[i,0]:=f[i,0]+t;
f[i,1]:=f[i,1]+max(f[j,0],0);
e:=next[e];
end;
p[i]:=true;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);readln;
for i:=1 to n do head[i]:=-1;
for i:=2 to n do
begin
readln(k);
add(k,i);
end;
fillchar(p,sizeof(p),false);
try(1);
writeln(max(f[1][0],f[1][1]));
end.

while (p1<>p2) do
begin
pp:=dep;
f[pp,1]:=f[pp,1]+max(a[pp],0);
if pp=1 then break;
f[fa[pp],0]:=f[fa[pp],0]+max(f[pp,1],f[pp,0]);
f[fa[pp],1]:=f[fa[pp],1]+f[pp,0];
dec(d[fa[pp]]);if d[fa[pp]]=0 then join(fa[pp]);
end;

var

a,fu,f:array[1..5002]of longint;

opt:array[1..5002,0..1]of longint;

n,i,j,ans:longint;

function max(a,b:longint):longint;

begin

if a>b then

exit(a)

else

exit(b);

end;

procedure dfs(x:longint);

var

i,a1,a0:longint;

begin

if f[x]=0 then

begin

opt[x,0]:=0;

opt[x,1]:=a[x];

end

else

begin

for i:=1 to n do

if fu[i]=x then

dfs(i);

a0:=0;

a1:=0;

for i:=1 to n do

if fu[i]=x then

begin

a0:=a0+max(opt[i,0],opt[i,1]);

a1:=a1+opt[i,0];

end;

opt[x,0]:=a0;

opt[x,1]:=a1+a[x];

end;

end;

begin

read(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n-1 do

begin

read(j);

fu[i+1]:=j;

f[j]:=1;

end;

dfs(1);

ans:=max(opt[1,1],opt[1,0]);

writeln(ans);

end.

var
a,fu,f:array[1..5002]of longint;
opt:array[1..5002,0..1]of longint;
n,i,j,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;
procedure dfs(x:longint);
var
i,a1,a0:longint;
begin
if f[x]=0 then
begin
opt[x,0]:=0;
opt[x,1]:=a[x];
end
else
begin
for i:=1 to n do
if fu[i]=x then
dfs(i);
a0:=0;
a1:=0;
for i:=1 to n do
if fu[i]=x then
begin
a0:=a0+max(opt[i,0],opt[i,1]);
a1:=a1+opt[i,0];
end;
opt[x,0]:=a0;
opt[x,1]:=a1+a[x];
end;
end;
begin

read(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n-1 do
begin
read(j);
fu[i+1]:=j;
f[j]:=1;
end;
dfs(1);
ans:=max(opt[1,1],opt[1,0]);
writeln(ans);
end.

var
a:array[1..5000] of longint;
opt:array[1..5000,0..1] of longint;
fa,hh:array[1..5000] of longint;
n:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
procedure init;
var
i,k:longint;
begin
fillchar(opt,sizeof(opt),0);
fillchar(hh,sizeof(hh),0);
read(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n-1 do
begin
read(k);
fa[i+1]:=k;
hh[k]:=1;
end;
end;
procedure dfs(x:longint);
var
i,ans0,ans1:longint;
begin
if hh[x]=0 then
begin
opt[x,0]:=0;
opt[x,1]:=a[x];
end
else
begin
for i:=1 to n do
if fa[i]=x then dfs(i);
ans0:=0;
ans1:=0;
for i:=1 to n do
if fa[i]=x then
begin
ans0:=ans0+max(opt[i,0],opt[i,1]);
ans1:=ans1+opt[i,0];
end;
opt[x,1]:=ans1+a[x];
opt[x,0]:=ans0;
end;
end;
procedure print;
var
ans:longint;
begin
ans:=max(opt[1,1],opt[1,0]);
writeln(ans);
end;
begin
init;
dfs(1);
print;
end.

明显树形动规。同意843279365，。，

设f[i] 第i个人上台后的最大搞笑值
设g[i] 第i个人不上台的最大搞笑值
因此有f[i]=MAX(f[i],g[j]) (j是i的儿子)
g[i]=MAX(g[i],f[j],g[j]) (j是i的儿子)

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 692 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 696 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 688 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 692 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 748 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 760 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 704 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 740 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 776 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 776 KiB, score = 10
Accepted, time = 154 ms, mem = 776 KiB, score = 100
代码
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>t[5005];
int a[5005],d[5005][3];

int dp(int i,int j) //j=1表示i参加，j=2表示i不参加
{
if(d[i][j]) return d[i][j];
if(j==1){
d[i][j]=a[i];
for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it)
d[i][j]+=dp(*it,2);
}
if(j==2){
for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it)
d[i][j]+=max(dp(*it,1),dp(*it,2));
}
return d[i][j];
}

int main()
{
ios::sync_with_stdio(false);
int n,dad;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)

{
cin>>dad;
t[dad].push_back(i);
}
cout<<max(dp(1,1),dp(1,2))<<endl;
return 0;
}

简单的树形动规
VijosEx via JudgeDaemon2/13.4.6.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 5 ms, mem = 98392 KiB, score = 10
测试数据 #1: Accepted, time = 1 ms, mem = 98392 KiB, score = 10
测试数据 #2: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
测试数据 #3: Accepted, time = 1 ms, mem = 98388 KiB, score = 10
测试数据 #4: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
测试数据 #5: Accepted, time = 7 ms, mem = 98392 KiB, score = 10
测试数据 #6: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
测试数据 #7: Accepted, time = 7 ms, mem = 98384 KiB, score = 10
测试数据 #8: Accepted, time = 4 ms, mem = 98384 KiB, score = 10
测试数据 #9: Accepted, time = 7 ms, mem = 98388 KiB, score = 10
Accepted, time = 46 ms, mem = 98392 KiB, score = 100

树形动规 但是用链表存图比较好，我用的是 邻接表 1..maxn 1..2000 过了