74 条题解
-
2
eurus LV 8 @ 7 年前
一道水题....典型树归
可参考“选课”，不同的是这题取了根节点就不能取左子树
不过我并不知道时间复杂度是怎么保证的（粗看要o（nm^2））orz……ps：貌似那个所有子节点的编号都比父节点的编号小的性质我没用到qwq
-
1
这题实际上是一个01背包，如果用树形动规去写的话很可能超时。
题目中有个特殊性质：所有子节点的编号都比父节点的编号小，通过这个性质我们可以倒序处理，用子节点的值求父节点的值；
last[i]表示所有被处理过的i的子节点中最后一个被处理的节点的编号
f[i][j]表示n到i中由i及其兄弟节点为根的树构成的森林用不超过j的费用的最大活跃值。#include<cstdio>
#include<algorithm>
#define ll long long
#define R register
using std::max;ll n,m,last[1025],p[1025][3],f[1025][110];
int main(){
scanf("%lld%lld",&n,&m);
for (R int i=0;i<3;++i)
for (R int j=i?1:2;j<=n;++j) scanf("%lld",&p[j][i]);
for (R int i=n;i;--i){
for (R int k=0;k<=m;++k){
if (!last[p[i][0]]){
f[i][k]=f[last[i]][k];
if (p[i][1]<=k) f[i][k]=max(f[i][k],p[i][2]);
}
else {
f[i][k]=f[last[p[i][0]]][k];
if (p[i][1]<=k) f[i][k]=max(f[i][k],p[i][2]+f[last[p[i][0]]][k-p[i][1]]);
for (R int t=0;t<=k;++t)
f[i][k]=max(f[i][k],f[last[i]][t]+f[last[p[i][0]]][k-t]);
}
}
last[p[i][0]]=i;
}
printf("%lld",f[1][m]);
} -
0
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>using namespace std;
int C[1030],E[1030],n,m;
int f[1030][120];
vector<int> tree[1030];void calc(int id){
int i,j,k,branch_n;
for(i = 0;i<(int)tree[id].size();i++)
calc(tree[id][i]);
for(i = 0;i<(int)tree[id].size();i++) {
branch_n = tree[id][i];
for(j = m;j>=0;j--) {//两个循环都要从后往前
for(k = j;k>=0;k--){
f[id][j] = max(f[id][j],f[branch_n][j-k]+f[id][k]);
}
}
}
for(i = m;i-C[id]>=0;i--) f[id][i] = max(f[id][i],E[id]);
}int main(){
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,tmp;
scanf("%d%d",&n,&m);
for(i = 2;i<=n;i++) {
scanf("%d",&tmp);
tree[tmp].push_back(i);
}
for(i = 1;i<=n;i++) scanf("%d",&C[i]);
for(i = 1;i<=n;i++) scanf("%d",&E[i]);
memset(f,0,sizeof(f));
calc(1);
printf("%d\n",f[1][m]);
return 0;
} -
0
-
0
everforever LV 10 @ 8 年前
多叉转二叉以后确实简介不少。。。（好吧实际也没多少。。。）
#include<cstdio>
#include<iostream>
#define MAXN 2005
#define MAXM 205
using namespace std;int n,m;
int use[MAXN][2];
int v[MAXN],w[MAXN];
int f[MAXN][MAXM];void dfs(int i)
{
if(i==0)return ;
dfs(use[i][0]),dfs(use[i][1]);
for(int j=0;j<=m;j++)
{
for(int g=0;g<=j;g++)
{
f[i][j]=max(f[i][j],f[use[i][0]][g]+f[use[i][1]][j-g]);
}
}
for(int j=m;j>=w[i];j--)
f[i][j]=max(f[i][j],f[use[i][1]][j-w[i]]+v[i]);
}int main()
{
scanf("%d%d",&n,&m);
int t1;
for(int i=2;i<=n;i++)
{
scanf("%d",&t1);
use[i][1]=use[t1][0];
use[t1][0]=i;
}
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
dfs(1);printf("%d",f[1][m]);
return 0;
} -
0
总感觉哪里不对 。。。基本和楼下一样了。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 2050
#define MAXM 200
#define LL long long
using namespace std;int n,m;
LL v[MAXN],w[MAXN];
int fst[MAXN],next[MAXN],to[MAXN],poi=0;
void add(int op,int ed)
{next[++poi]=fst[op],fst[op]=poi,to[poi]=ed;return ;}LL max(LL a,LL b){return a>b? a:b;}
LL f[MAXN][MAXM],tmp[MAXN][MAXM];
int vis[MAXN];void dfs(int x)
{
vis[x]=1;
for(int i=fst[x];i;i=next[i])if(!vis[to[i]])dfs(to[i]);
memset(tmp,0,sizeof(tmp));
int h=0;
for(int i=fst[x];i;i=next[i])
{
h++;
for(int j=0;j<=m;j++)
{
for(int g=0;g<=j;g++)
{
tmp[h][j]=max(tmp[h][j],tmp[h-1][g]+f[to[i]][j-g]);
}
}
}
for(int i=0;i<=m;i++)
{
f[x][i]=tmp[h][i];
if(i>=w[x])f[x][i]=max(f[x][i],v[x]);
}
}int main()
{
scanf("%d%d",&n,&m);
int t1;
for(int i=2;i<=n;i++)
{
scanf("%d",&t1);
add(t1,i);
}
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&v[i]);dfs(1);
printf("%lld",f[1][m]);
return 0;
} -
0
feng_lingsong LV 9 @ 9 年前
数据给的109就是吓人的，还以为是10^9orz.....
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define rep(i, x, y) for (int i = x; i <= y; ++i)using namespace std;
const int maxn = 1 << 11, maxm = 1 << 7;
struct Node {
int nextNode;
Node *next;
} *N[maxn], pool[maxn << 1];
int pool_cnt;
int n, m;
int c[maxn], e[maxn];void addedge(int x, int y) {
Node *p = &pool[++pool_cnt];
*p = (Node){y, N[x]};
N[x] = p;
}
int vis[maxn];
int f[maxn][maxm], g[maxn][maxm], cnt[maxn], son[maxn][maxn];void dfs(int i) {
vis[i] = true;
for (Node *p = N[i]; p; p = p->next) {
if (!vis[p->nextNode]) {
son[i][++cnt[i]] = p->nextNode;
dfs(p->nextNode);
}
}
memset(f, 0, sizeof (f));
rep(j, 1, cnt[i]) rep(k, 0, m) rep(_k, 0, k)
f[j][k] = max(f[j][k], f[j - 1][_k] + g[son[i][j]][k - _k]);
rep(j, 0, m) {
g[i][j] = f[cnt[i]][j];
if (c[i] <= j) g[i][j] = max(e[i], g[i][j]);
}
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &n, &m);
rep(i, 2, n) {
int y;
scanf("%d", &y);
addedge(i, y); addedge(y, i);
}
rep(i, 1, n) scanf("%d", &c[i]);
rep(i, 1, n) scanf("%d", &e[i]);
dfs(1);
printf("%d\n", g[1][m]);
return 0;
} -
0
wang_yanheng LV 10 @ 9 年前
多叉树转二叉树后记忆化搜索，具体选择请看代码及注释。（由于转成二叉树后，根与左子树是父子关系，根与右子树是兄弟关系，所以选了根还可以选右子树，但一定不能选左子树）时间不太好看，最慢的一个点要900+ms，不过勉强能过。
#include <stdio.h>
#define LOWER_BOUND -100000000
#define MAX_NUM 1500struct{
int left, right, cost, value;
} tree[MAX_NUM];
int lastChild[MAX_NUM];
int f[MAX_NUM][110]; //f[root][budget]int Max(int a, int b){
return a>b ? a:b;
}
int search(int root, int budget){
int i;
if(f[root][budget]>LOWER_BOUND)
return f[root][budget];
if(budget<0)
return LOWER_BOUND;
//**if root is chosen, its left child cannot be chosen; its right child can be chosen**
if(budget >= tree[root].cost){
//---chooose root---
f[root][budget] = tree[root].value; //choose root only
if(tree[root].right >= 0)
f[root][budget] = Max(f[root][budget], search(tree[root].right, budget-tree[root].cost) + tree[root].value); //right & root
}
//---not choose root---
if(tree[root].right >= 0)
f[root][budget] = Max(f[root][budget], search(tree[root].right, budget)); //right only
if(tree[root].left >= 0)
f[root][budget] = Max(f[root][budget], search(tree[root].left, budget)); //left only
if(tree[root].left >= 0 && tree[root].right >= 0){
for(i=0; i<=budget; i++)
f[root][budget] = Max(f[root][budget], search(tree[root].left, i) + search(tree[root].right, budget-i)); //left & right
}
return f[root][budget];
}
int main(){
int num, limit;
int i, k;
scanf("%d %d", &num, &limit);
for(i=0; i<num; i++){
for(k=0; k<=limit; k++)
f[i][k] = LOWER_BOUND;
tree[i].left = tree[i].right = -1;
lastChild[i] = -1;
}
for(i=1; i<num; i++){
scanf("%d", &k);
--k;
if(lastChild[k]<0)
tree[k].left = i;
else
tree[lastChild[k]].right = i;
lastChild[k] = i;
}
for(i=0; i<num; i++)
scanf("%d", &tree[i].cost);
for(i=0; i<num; i++)
scanf("%d", &tree[i].value);
printf("%d\n", search(0, limit));
return 0;
} -
0
williamking5 LV 8 @ 11 年前
一定要注意有c[i]=0
###Block Code
var
i,j,k,m,n,total:longint;
p,ii:longint;
fa,l,r:array[1..1024] of int64;
f:array[1..1024,0..109] of int64;
g:array[0..1024,0..109] of int64;
c,e:array[1..1024] of int64;
begin
readln(n,total);
fillchar(l,sizeof(l),0);
fillchar(r,sizeof(r),0);for i:=2 to n do
begin
read(fa[i]);r[i]:=l[fa[i]];
l[fa[i]]:=i;
end;for i:=1 to n do
read(c[i]);for i:=1 to n do
read(e[i]);for ii:=n downto 1 do
begin
i:=l[ii];
p:=0;
fillchar(g,sizeof(g),0);
while i<>0 do
begin
inc(p);
for j:=0 to total do
begin
for k:=0 to total do
begin
if j-k<0 then continue;if g[p][j]<g[p-1][j-k]+f[i][k] then
g[p][j]:=g[p-1][j-k]+f[i][k];
end;
end;i:=r[i];
end;for i:=0 to total do
f[ii][i]:=g[p][i];for i:=c[ii] to total do
if f[ii][i]<e[ii] then
f[ii][i]:=e[ii];
end;writeln(f[1][total])
end. -
0
sliversmall LV 5 @ 15 年前
利用惯性思维吓人……才110，不是10^9
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
我的方法是o（n*m）的
不是树形dp -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 41ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 56ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：218ms练练树归……
=======================puppy的分割线=======================
program v1418;
var l,r,c,e:array[0..1030] of longint;
f:array[0..1030,0..110] of longint;
b:array[0..1030,0..110] of boolean;
i,n,m,x:longint;
function max(p,q:longint):longint;
begin
if p>q then exit(p) else exit(q);
end;
procedure dp(i,j:longint);
var k:longint;
begin
if (i=0) then exit;
if b then exit;
if (j>=c[i])and(e[i]>0)
then begin
dp(r[i],j-c[i]);
f:=f[r[i],j-c[i]]+e[i];
end;
for k:=0 to j do
begin
dp(l[i],k);
dp(r[i],j-k);
f:=max(f,f[l[i],k]+f[r[i],j-k]);
end;
b:=true;
end;
begin
readln(n,m);
for i:=2 to n do
begin
read(x);
if l[x]=0 then l[x]:=i
else begin
r[i]:=l[x];
l[x]:=i;
end;
end;
for i:=1 to n do read(c[i]);
for i:=1 to n do read(e[i]);
fillchar(b,sizeof(b),false);
dp(1,m);
writeln(f[1,m]);
end. -
0
LP.Fighting LV 10 @ 15 年前
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 72ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 25ms
├ 测试数据 09：答案正确... 259ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：356ms好慢的treedp...
我是sb...第一次没加记忆化就交了...TLE...
于是想了两个剪枝
if jsum[i] then j:=sum[i];
min[i]是以i为根结点的子树c的最小值
sum[i]是以i为根结点的子树c的和
照样TLE...
静态差错...发现少了最重要的
if f0 then exit(f);
果然什么剪枝都比不上记忆化...
eurus
LV 8
@ 7 年前
