74 条题解
-
2
eurus LV 8 @ 2017-09-02 11:20:42
一道水题....典型树归
可参考“选课”，不同的是这题取了根节点就不能取左子树
不过我并不知道时间复杂度是怎么保证的（粗看要o（nm^2））orz……#include<bits/stdc++.h> using namespace std; int lson[1030], rson[1030], c[1030], e[1030], f[1030][115]; int dfs(int u, int x){ if(u<0) return 0; //没人可以加入了 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)); if(x>=c[u]) ret=max(ret, e[u]+dfs(rson[u], x-c[u]));//根节点选 return f[u][x]=ret; } int main() { memset(f, -1, sizeof(f)); memset(lson, -1, sizeof(lson)); memset(rson, -1, sizeof(rson));//这两个-1是判断有没有儿子 int n, m; cin>>n>>m; for(int i=2;i<=n;i++){ int u; scanf("%d", &u); rson[i]=lson[u]; lson[u]=i; } for(int i=1;i<=n;i++) scanf("%d", &c[i]); for(int i=1;i<=n;i++) scanf("%d", &e[i]); cout<<dfs(1, m)<<endl; //1保证是根 return 0; }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]);
} -
1
这道题与经典的公司聚会不同，因为上司的定义由父结点改为了所有祖先。这样问题也由树形dp变为了01背包。
由于题目中有一个非常重要的条件，“员工的编号会大于他的直接上司的编号”。这使得我们可以直接循环而不用建立树结构。用F来表示
1)结点I的子树(不包括I结点)用J的花费可获得的最大值 在未循环到I时
2)结点I的子树(可能包括I结点)用J的花费可获得的最大值 在循环到I以后1)在循环到I结点之前，已经把I结点的所有儿子处理过了，所以在处理I之前就可以先用I结点儿子的信息计算不取I结点所能获得的最大值。即在循环到I结点的儿子X时，把F[X,K](0
-
0
#include <bits/stdc++.h> #include <climits> using namespace std; #define maxxn 1100 #define maxxm 120 int N, M, C[maxxn], E[maxxn]; int F[maxxn][maxxm]; struct Edges{ int l, r; }T[maxxn]; void Putin() { cin >> N >> M; memset(T, 0, sizeof(T)); int root; for(int i = 2; i <= N; i++){ cin >> root; T[i].r = T[root].l; T[root].l = i; } for(int i = 1; i <= N; i++) cin >> C[i]; for(int i = 1; i <= N; i++) cin >> E[i]; for(int i = 0; i <= 1025; i++) for(int k = 0; k <= 110; k++) F[i][k] = -(1024 * 1024); } inline void DP_dfs(int root) { if(root == 0) return; DP_dfs(T[root].l), DP_dfs(T[root].r); for(int k = M; k >= C[root]; k--) F[root][k] = max(F[root][k], E[root]);//只选择root; if(T[root].l > 0 && T[root].r > 0) for(int i = 0; i <= M; i++) for(int k = 0; k <= i; k++) F[root][i] = max(F[T[root].l][k] + F[T[root].r][i - k], F[root][i]); //不选root，选择左子树和右子树; if(T[root].l > 0) for(int i = 0; i <= M; i++) F[root][i] = max(F[root][i], F[T[root].l][i]);//不选root，只选择左子树; if(T[root].r > 0) for(int i = 0; i <= M; i++){ if(i - C[root] >= 0) F[root][i] = max(F[root][i], F[T[root].r][i - C[root]] + E[root]); //选择root和右子树; F[root][i] = max(F[T[root].r][i], F[root][i]);//只选择右子树; } return; } int main() { Putin(); DP_dfs(1); cout << F[1][M] << endl; return 0; } -
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
Sky1231 (sky1231) LV 10 @ 2017-01-29 15:44:21
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node1 { int h,c,e,sn,s[1025]; }a[1025]; int n,m,f[1025][110]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { a[i].sn=0; memset(a[i].s,0,sizeof(a[i].s)); } a[1].h=0; for (int i=2;i<=n;i++) { scanf("%d",&a[i].h); a[a[i].h].s[++a[a[i].h].sn]=i; } for (int i=1;i<=n;i++) scanf("%d",&a[i].c); for (int i=1;i<=n;i++) scanf("%d",&a[i].e); memset(f,0,sizeof(f)); for (int i=n;i>=1;i--) { for (int k=1;k<=a[i].sn;k++) for (int j=m;j>=0;j--) for (int t=0;t<=j;t++) f[i][j]=max(f[i][j],f[i][j-t]+f[a[i].s[k]][t]); for (int j=m;j>=a[i].c;j--) f[i][j]=max(f[i][j],a[i].e); } printf("%d\n",f[1][m]); }-
很H2O的背包
-
-
0
//迭代深搜 #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAXN = 1024 + 5; const int MAXM = 109 + 5; int n, m, ec = 0, fa, c[MAXN], e[MAXN], fst[MAXN], to[MAXN << 1], next[MAXN]; inline void add(int f, int t) { to[++ec] = t; next[ec] = fst[f]; fst[f] = ec; } int f[MAXN][MAXM], g[MAXN][MAXM], cur[MAXN], s[MAXN], top = 0; bool vis[MAXN]; int main() { memset(vis, 0, sizeof(vis)); scanf("%d%d", &n, &m); for (int i = 2; i <= n; i++) { scanf("%d", &fa); add(fa, i); } for (int i = 1; i <= n; i++)scanf("%d", &c[i]); for (int i = 1; i <= n; i++)scanf("%d", &e[i]); s[top++] = 1; vis[1] = true; memcpy(cur, fst, sizeof(fst)); while (top) { int u = s[top - 1]; vis[u] = true; if (cur[u]) { int v = to[cur[u]]; if (!vis[v])s[top++] = v; cur[u] = next[cur[u]]; } else { memset(f, 0, sizeof(f)); int h = 0; for (int i = fst[u]; i; i = next[i]) { h++; for (int j = 0; j <= m; j++) for (int k = 0; k <= j; k++) f[h][j] = max(f[h][j], f[(h - 1)][k] + g[to[i]][j - k]); } memcpy(g[u], f[h], sizeof(f[h])); for (int j = 0; j <= m; j++)if (j >= c[u])g[u][j] = max(g[u][j], e[u]); top--; } } printf("%d\n", g[1][m]); return 0; } -
0
everforever LV 10 @ 2016-05-10 16:02:50
多叉转二叉以后确实简介不少。。。（好吧实际也没多少。。。）
#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 @ 2015-12-11 23:35:16
数据给的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 @ 2015-08-15 08:36:23
多叉树转二叉树后记忆化搜索，具体选择请看代码及注释。（由于转成二叉树后，根与左子树是父子关系，根与右子树是兄弟关系，所以选了根还可以选右子树，但一定不能选左子树）时间不太好看，最慢的一个点要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 @ 2013-10-29 22:43:46
一定要注意有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 @ 2010-04-01 12:13:01
利用惯性思维吓人……才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 @ 2009-08-31 13:32:20
编译通过...
├ 测试数据 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
@ 2017-09-02 11:20:42
