JZOJ5344. 【NOIP2017模拟9.3A组】摘果子

题目大意

就是有一堆物品，每个物品都有代价与价值，某些物品一定要在选了另外一些物品之后才能选，求最大价值。

题解

很显然是树形dp，但是这里的n是2000，将多叉树转为二叉树的方法是不行的。
另外一种方法，就是用dfs序。

我们设$f_{i,j}$ 表示dfs序的第i个，代价为j的最大值。
转移有两种情况：
1、当前不选，那么就直接跳过它的子树：$f_{i+size_x,j}$ x表示dfs序的第i个对应的数。
2、当前选，就从后面一个转移过来：$f_{i+1,j-w_x}+v_x$

那么最后的时间复杂度就是O(nm)的。

将多叉树转为二叉树的方法

#include
#include
#include
#include
#include 
#include 
#include 
#include 
#define ll long long
#define N 2003
#define db double
#define P putchar
#define G getchar
#define mo 9901
using namespace std;
char ch;
void read(int &n)
{n=0;ch=G();while((ch<'0' || ch>'9') && ch!='-')ch=G();ll w=1;if(ch=='-')w=-1,ch=G();while('0'<=ch && ch<='9')n=n*10+ch-'0',ch=G();n*=w;
}void write(int x)
{if(x>9) write(x/10);P(x%10+'0');
}int f[N][N],n,m,v[N],w[N];
int l[N],r[N],x,y;
int son[N][N],ans;
int next[N*2],b[N],a[N*2],tot;
bool bz[N];void ins(int x,int y)
{next[++tot]=b[x];a[tot]=y;b[x]=tot;
}void dfs(int x,int mx)
{if(mx<=0)return;if(l[x])dfs(l[x],mx-w[x]);if(r[x])dfs(r[x],mx);for(int k=w[x];k<=mx;k++){for(int i=0;i<=k-w[x];i++)if(f[l[x]][i]+f[r[x]][k-w[x]-i]+v[x]>f[x][k])f[x][k]=f[l[x]][i]+f[r[x]][k-w[x]-i]+v[x];}for(int k=1;k<=mx;k++) if(f[r[x]][k]>f[x][k])f[x][k]=f[r[x]][k];
}void dg(int x)
{for(int i=b[x];i;i=next[i])if(bz[a[i]]){bz[a[i]]=0;son[x][++son[x][0]]=a[i];dg(a[i]);}
}int main()
{read(n);read(m);for(int i=1;i<=n;i++)read(v[i]),read(w[i]);for(int i=1;imemset(bz,1,sizeof(bz));bz[1]=0;dg(1);for(int i=1;i<=n;i++){l[i]=son[i][1];for(int j=2;j<=son[i][0];j++)r[son[i][j-1]]=son[i][j];}dfs(1,m);for(int i=w[1];i<=m;i++)ans=f[1][i]>ans?f[1][i]:ans;write(ans),putchar('\n');
}

dfs许的方法

#include
#include
#include
#include
#include 
#include 
#include 
#include 
#define ll long long
#define N 2003
#define db double
#define P putchar
#define G getchar
#define mo 9901
using namespace std;
char ch;
void read(int &n)
{n=0;ch=G();while((ch<'0' || ch>'9') && ch!='-')ch=G();ll w=1;if(ch=='-')w=-1,ch=G();while('0'<=ch && ch<='9')n=n*10+ch-'0',ch=G();n*=w;
}int max(int a,int b)
{return a>b?a:b;
}void write(int x)
{if(x>9) write(x/10);P(x%10+'0');
}int f[N][N],n,m,v[N],w[N];
int l[N],r[N],x,y,ans,size[N];
int next[N*2],b[N],a[N*2],tot;
int dfn[N],g[N],id;
bool bz[N];void ins(int x,int y)
{next[++tot]=b[x];a[tot]=y;b[x]=tot;
}void dg(int x)
{size[x]=1;dfn[x]=++id;g[id]=x;for(int i=b[x];i;i=next[i])if(bz[a[i]]){bz[a[i]]=0;dg(a[i]);size[x]+=size[a[i]];}
}int main()
{read(n);read(m);for(int i=1;i<=n;i++)read(v[i]),read(w[i]);for(int i=1;imemset(bz,1,sizeof(bz));bz[1]=0;dg(1);for(int i=n;i;i--){x=g[i];for(int j=1;j<=m;j++){f[i][j]=max(0,f[i+size[x]][j]);if(j>=w[x])f[i][j]=max(f[i][j],f[i+1][j-w[x]]+v[x]);}}for(int i=w[1];i<=m;i++)ans=f[1][i]>ans?f[1][i]:ans;write(ans),putchar('\n');
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！