题解 - Vijos

8

/*
一道树形dp，因为每门课的先修课最多只有一节，则说明这是个树结构
对于读入的边，我们先将多叉树建立成二叉树
原则是左儿子右兄弟
然后再定义状态f表示以i课程为父亲结点的子树上选j门课程的最多学分
则有状态转移方程
f[i][j]=max(f[left][j-k-1]+f[right][k]+score[i](0<=k<=j-1),f[right][j])
方程含义：1、取当前i节点，则剩下的j-1们课程，在孩子中选j-k-1门，在兄弟中选k门。
          2、不取当前节点，则只能在兄弟中选j门。
k用来表示的是分别分配在某个节点上的左右子树的选择课程树
注意还有个f[right][j]即表示不选这门课程而选择它的右兄弟
原理上两种情况是根本上相同可合并的但是实际实现中没有那么方便
所以我们可以自顶向下用dfs进行树的遍历递归求解
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=305;
struct node
{
    int l,r,v;
}tree[maxn];
int n,m;
int f[maxn][maxn];

int dfs(int x,int y)
{
    if(!y||x<0)
        return 0;
    if(!x)
        return dfs(tree[x].l,y);
    if(f[x][y])
        return f[x][y];
    f[x][y]=dfs(tree[x].r,y);
    for(int i=0;i<y;i++)
        f[x][y]=max(f[x][y],dfs(tree[x].l,i)+tree[x].v+dfs(tree[x].r,y-i-1));
    return f[x][y];
}

int main()
{
    memset(tree,-1,sizeof(tree));
    cin>>n>>m;
    int fa,v;
    for(int i=1;i<=n;i++)
    {
        cin>>fa>>v;
        tree[i].r=tree[fa].l;
        tree[fa].l=i;
        tree[i].v=v;
    }
    cout<<dfs(0,m)<<endl;//0表示入口，0的子节点表示第一层
    return 0;
}

2

eurus LV 8 @ 7 年前

最基础的树形dp
根据从属关系建立二叉树，左孩子右兄弟（详见代码）
再从根节点记忆化搜索即可

#include<bits/stdc++.h>
using namespace std;

int lson[305], rson[305], val[305], f[305][305];

int dfs(int u, int x){
    if(x==0) return 0;                 //选课选完了
    if(u==-1) return -987654321;       //选课数目没达到m
    if(f[u][x]!=-1) return f[u][x];
    int ret=0;
    for(int i=0;i<x;i++)
            ret=max(ret, dfs(lson[u], i)+dfs(rson[u], x-i-1));
    ret+=val[u];                       //以上3行是选u节点的最优解
    ret=max(ret, dfs(rson[u], x));     //不选u
    return f[u][x]=ret;
}

int main()
{
    memset(f, -1, sizeof(f));
    memset(lson, -1, sizeof(lson));
    memset(rson, -1, sizeof(rson));
    int n, m; cin>>n>>m;
    for(int i=1;i<=n;i++){
            int u;
            cin>>u>>val[i];
            rson[i]=lson[u];
            lson[u]=i;
    }       
    cout<<dfs(lson[0], m)<<endl;        //lson[0]是根
    return 0;
}

1

lbz888 LV 7 @ 7 年前

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,m;
int l[302],r[302],last[302];
int val[302];
int max(int a,int b)
{
return a>b?a:b;
}
void build(int x,int y)
{
if(l[y]==-1) l[y]=x;
else r[last[y]]=x;
last[y]=x;
}
int f[302][302];// f[i][j] : 以 i 为根的子树中选j门课最多学分
int ans=0;
int work(int pos,int k)
{
if(pos<0||k<=0) return 0;
if(f[pos][k]!=-1) return f[pos][k];
f[pos][k]=work(r[pos],k);
for(int i=0;i<=k-1;i++)
{
f[pos][k]=max(f[pos][k],work(l[pos],i)+work(r[pos],k-i-1)+val[pos]);
}
return f[pos][k];
}
int main()
{
int i,j;
memset(l,-1,sizeof(l));
memset(f,-1,sizeof(f));
memset(r,-1,sizeof(r));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
int x;
scanf("%d%d",&x,&val[i]);
build(i,x);//i 的父亲是 x
}
printf("%d",work(0,m+1));
return 0;
}

1

hahayang LV 10 @ 7 年前

树形dp秒杀

type
  node=record
    s,b,x:integer
  end;
var
  tree:array[0..300] of node;
  f:array[0..300,0..301] of integer;
  n,m,i,a,b:integer;
function max(a,b:integer):integer;
  begin
    if a>b then exit(a)
    else exit(b)
  end;
function last(x:integer):integer;
  begin
    while tree[x].b>0 do x:=tree[x].b;
    exit(x)
  end;
function dp(root,q:integer):integer;
  var
    i,s:integer;
  begin
    if f[root,q]>0 then exit(f[root,q]);
    if q=0 then exit(0);
    if tree[root].s=0 then if tree[root].b=0 then f[root,q]:=tree[root].x
    else f[root,q]:=max(dp(tree[root].b,q-1)+tree[root].x,dp(tree[root].b,q))
    else if tree[root].b=0 then f[root,q]:=dp(tree[root].s,q-1)+tree[root].x
    else begin
      s:=0;
      for i:=0 to q-1 do s:=max(s,dp(tree[root].s,i)+dp(tree[root].b,q-i-1));
      inc(s,tree[root].x);
      s:=max(s,dp(tree[root].b,q));
      f[root,q]:=s
    end;
    exit(f[root,q])
  end;
begin
  readln(n,m);
  fillchar(tree,sizeof(tree),0);
  for i:=1 to n do begin
    readln(a,b);
    if tree[a].s=0 then tree[a].s:=i
    else tree[last(tree[a].s)].b:=i;
    tree[i].x:=b
  end;
  fillchar(f,sizeof(f),0);
  write(dp(0,m+1))
end.

1

larryzhong LV 9 @ 7 年前

#include <iostream>
#include <vector>
using namespace std;

const int maxn = 310;
int f[maxn][maxn];

// 邻接表
struct node {
    int cost;
    vector<int> child;
} tree[maxn];

// 搜索以 tree[x] 为根且能选 y 门课程的最大值
void dfs(int x, int y) {
    for (int i = 0; i < tree[x].child.size(); i++) {
        int tmp = tree[x].child[i];
        for (int j = 0; j < y; j++)
            f[tmp][j] = f[x][j] + tree[tmp].cost;
        dfs(tmp, y - 1);
        for (int j = 1; j <= y; j++)
            f[x][j] = max(f[x][j], f[tmp][j - 1]);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int father;
        cin >> father;
        tree[father].child.push_back(i);
        cin >> tree[i].cost;
    }
    dfs(0, m);
    cout << f[0][m] << endl;
    return 0;
}

0

33-hope LV 3 @ 3 年前

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100;
int n,m;
int y;
int d = 1;
void DP(int u);
vector <int> tree[MAXN];
int f[MAXN][MAXN];//节点i之后选了j门课的最大学分值。
int a[MAXN/10][MAXN/10]; // 存储元素
void init(){
scanf("%d %d", &n, &m); //n为共有n门课程，需要选择m门课程
for(int i=1;i<=n;++i){
//f[i][1]代表的就是以当前节点为根节点只选择一门课的学分，也就是该门课本身的学分，即v[i]
scanf("%d %d",&y,&f[i][1]);
tree[y].push_back(i);
}
DP(0);
}
/**
* 实现DP问题，为了有统一的根节点，设置原始结点为0，即所有课程根节点都是课程为0的
* 所以下面的实现过程中，最终的学分最大为f[0][m+1]
* @param u
*/
void DP(int u){
for (int i = 0; i < tree[u].size(); ++i) {
int son = tree[u][i];//节点u的子节点
printf("%d\n", son);
DP(son);
for (int j = m + 1; j >= 1; --j) {
for (int k = 0; k < j; ++k) {
f[u][j] = max(f[u][j], f[son][k] + f[u][j - k]);

}
}
}
}
int main(){
init();
printf("%d",f[0][m+1]);
return 0;
}

0

Sky1231 (sky1231) LV 10 @ 6 年前

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    struct lesson
    {
        ll v,fa;
        vector<ll> s;
    }a[300+1];
    
    ll n,m;
    ll f[300+1][300+1];
    
    void work(ll now,ll cnt)
    {
        for (ll i=1;i<=n;i++)
            f[now][i]=a[now].v;
        for (ll i=0;i<a[now].s.size();i++)
        {
            work(a[now].s[i],cnt+1);
            for (ll j=m-cnt;j>0;j--)
                for (ll k=0;k<j;k++)
                    f[now][j]=max(f[now][j],f[a[now].s[i]][k]+f[now][j-k]);
        }
    }
    
    void main()
    {
        while (~scanf("%lld%lld",&n,&m))
        {
            for (ll i=1;i<=n;i++)
                a[i].s.clear();
            for (ll i=1;i<=n;i++)
            {
                scanf("%lld%lld",&a[i].fa,&a[i].v);
                a[a[i].fa].s.push_back(i);
            }
            memset(f,0,sizeof(f));
            m++;
            work(0,0);
            printf("%lld\n",f[0][m]);
        }
    }
};

int main()
{
    dts::main();
}

0

bonboru93 LV 8 @ 7 年前

n只有300，搞一个不递归的写法过掉。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int f[301], v[301], s[301] = {0}, **ans, **new_ans;

int** mymallo()
{
    int**ptr = (int**)malloc(301 * sizeof(int*));
    for (int i = 0; i < 301; i++)
    {
        ptr[i] = (int*)malloc(301 * sizeof(int));
        memset(ptr[i], -1, 301 * sizeof(int));
    }
    return ptr;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    ans = mymallo();
    new_ans = mymallo();
    ans[0][0] = new_ans[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &f[i], &v[i]);
        s[f[i]]++;
        ans[i][0] = new_ans[i][0] = 0;
    }
    int tot = 0;
    while (tot < n)
    {
        for (int i = 1; i <= n; i++)
            if (s[i] == 0)
            {
                for (int j = 0; j < m; j++)
                    if (ans[i][j] >= 0)
                        for (int k = j + 1; k <= m; k++)
                            if ((ans[f[i]][k - j - 1] >= 0) && (ans[f[i]][k - j - 1] + ans[i][j] + v[i] > new_ans[f[i]][k]))
                                new_ans[f[i]][k] = ans[f[i]][k - j - 1] + ans[i][j] + v[i];
                s[i] = -1;
                s[f[i]]--;
                tot++;
                for (int t1 = 0; t1 < 301; t1++)
                    for (int t2 = 0; t2 < 301; t2++)
                        ans[t1][t2] = new_ans[t1][t2];
                int **t = ans; ans = new_ans; new_ans = t;
            }
    }
    printf("%d", ans[0][m]);
}

0

Zechariah LV 7 @ 7 年前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define N 1000+10

using namespace std;
struct Node{
int left;
int right;
int data;
}a[N];
int f[N][N],child[N];
int n,q;
bool root[N];
//记忆化搜索
int dfs(int x,int num)
{
if (f[x][num])return f[x][num];
if (num==0||x==0)return 0;
f[x][num]=dfs(a[x].right,num);
for (int k=0;k<=num-1;++k)
{
f[x][num]=max(f[x][num],dfs(a[x].left,k)+dfs(a[x].right,num-1-k)+a[x].data);
}
return f[x][num];
}

int main(void)
{
scanf("%d%d",&n,&q);
for (int i=1;i<=n;++i)
{
int s,d;
scanf("%d%d",&s,&d);
a[i].right=a[s].left;
a[s].left=i;
a[i].data=d;
}
printf("%d",dfs(a[0].left,q));
return 0;
}

0

ACsKy LV 4 @ 15 年前

发现用C做的好像挺少的，贴下...

#include

using namespace std;

const int N = 305;

int isLeaf[N], Leaf[N];

int fath[N];

int DP[N][N];

int Q[N];

void Dp(int p1, int p2, int c) {

for(int i = c; i >= 2; i --) {

for(int j = i - 1; j > 0; j --) {

DP[p2][i] = max(DP[p2][i], DP[p2][i - j] + DP[p1][j]);

}

}

}

int main() {

int n, m, front = 0, back = 0, buf, f;

scanf("%d%d", &n, &m);

m ++;

for(int i = 1; i

0

Volom@nder LV 8 @ 15 年前

var

f:array[0..300,0..300]of integer;

left,right,w:array[0..300]of integer;

n,m,i,dad,j:integer;

function dp(p,k:integer):integer;

var

i,temp,max:integer;

begin

if f[p,k]-1 then exit(f[p,k]);

if (p=0) then exit(0); {it means it's the end of a tree}

max:=0;

for i:=0 to (k-1) do begin

temp:=dp(left[p],i)+dp(right[p],k-i-1)+w[p];

if temp>max then max:=temp;

end;

temp:=dp(right[p],k);

if temp>max then max:=temp;

f[p,k]:=max;

exit(max);

end;

begin

readln(n,m);

fillchar(f,sizeof(f),255);

for i:=1 to n do begin

readln(dad,w[i]);

right[i]:=left[dad];

left[dad]:=i;

f:=0;

end;

writeln(dp(left[0],m));

end.

一点小错误 w[i]... 导致悲剧了两个小时。。。。以后发现不行立刻重写！！！！

0

kun LV 8 @ 15 年前

program vijos_1180;

type

tree=record

l,r:longint;

end;

var

w,fg:array[1..300]of longint;

a:array[0..300]of tree;

f:array[0..30,0..30]of longint;

n,m,i,j,k:longint;

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

begin

if a>b then exit(a)

else exit(b);

end;

procedure work(i,j:longint);

var

k:longint;

begin

if f>=0 then exit;

work(a[i].r,j);

f:=f[a[i].r,j];

for k:=0 to j-1 do

if (j-k-1>=0)and(j-k-1

0

dsy LV 8 @ 15 年前

var

n,m,i,j,x:longint;

right,left,w:array[0..2000]of longint;

f:array[0..1000,0..500]of longint;

t:array[0..1000,0..500]of boolean;

procedure addbrother(brother,son:longint);

begin

if right[brother]=0 then right[brother]:=son

else addbrother(right[brother],son);

end;

procedure addson(father,son:longint);

begin

if left[father]=0 then left[father]:=son

else addbrother(left[father],son);

end;

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

begin

if a>b then exit(a) else exit(b);

end;

procedure doit(now,j:longint);

var k:longint;

begin

if (j=0)or (now=0) then exit;

if not(t[right[now],j]) then doit(right[now],j);

f[now,j]:=f[right[now],j];

for k:=0 to j-1 do

begin

if not(t[left[now],k]) then doit(left[now],k);

if not(t[right[now],j-k-1]) then doit(right[now],j-k-1);

f[now,j]:=max(f[now,j],f[left[now],k]+f[right[now],j-k-1]+w[now]);

end;

t[now,j]:=true;

end;

begin

readln(n,m);

for i:=1 to n do

begin

readln(x,w[i]);

addson(x,i);

end;

for i:=0 to m do t[0,i]:=true;

for i:=1 to n do

for j:=1 to m do doit(i,j);

writeln(f[left[0],m]);

end.

0

zmc1213 LV 8 @ 15 年前

编译通过...

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

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

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

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

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

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

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

小庆一下60题~~~

0

天花乱坠X LV 8 @ 15 年前

编译通过...

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

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

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

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

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

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

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

program p1180;

var n,m,dad,root:longint;

right,left,cost:array[0..1000]of longint;

f:array[0..1000,0..1000]of longint;

procedure init;

var i:longint;

begin

readln(n,m);

for i:=1 to n do

begin

readln(dad,cost[i]);

right[i]:=left[dad];

left[dad]:=i;

if dad=0 then root:=i;

end;

end;

function max(x,y:longint):longint;

begin

if x>y then exit(x);exit(y);

end;

procedure treedp(k,l:longint);

var i:longint;

begin

if (l=0)or(k=0) then exit;

if f[k,l]>0 then exit;

treedp(right[k],l);

f[k,l]:=f[right[k],l];

for i:=0 to l-1 do

begin

treedp(left[k],i);

treedp(right[k],l-i-1);

f[k,l]:=max(f[k,l],f[left[k],i]+f[right[k],l-i-1]+cost[k]);

end;

end;

begin

init;

fillchar(f,sizeof(f),0);

treedp(root,m);

writeln(f[root,m]);

end.

0

wll969 LV 8 @ 15 年前

注意了。。转二叉树后，根节点0和孩子没有从属关系。。。

0

song19931218 LV 9 @ 15 年前

编译通过...

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

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

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

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

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

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

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

多叉转二叉

0

pascalcoco LV 8 @ 15 年前

编译通过...

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

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

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

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

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

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

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

dp程序就是短啊就是短～～

感谢lx Cambridge 神牛的方程提醒。。

给段核心的

if x=0 then exit;

if f[x,y]>0 then exit;

if y=0 then

begin

f[x,y]:=0;

exit;

end;

if tree[x][1]0 then

begin

treedp(tree[x][1],y);

f[x,y]:=f[tree[x][1],y];

end;

for i := 0 to y-1 do

begin

treedp(tree[x][0],i);

treedp(tree[x][1],y-i-1);

if f[tree[x][0],i]+score[x]+f[tree[x][1],y-i-1]>f[x,y]

then f[x,y]:=f[tree[x][0],i]+score[x]+f[tree[x][1],y-i-1];

end;

0

大走文 LV 10 @ 15 年前

不用转二叉也能秒

0

whaha LV 9 @ 15 年前

水题

题解

151 条题解

选课

信息

状态

开发

支持

题解

151 条题解

选课

信息

状态

开发

支持

还没有账户？

登录