有线电视网
这是一个树上的分组背包。
我们设dp[i][j]表示在以i为根的子树中，满足j个客户的需求所能获得的最大收益，
那么在最终求最多客户时，只要求最大的dp[1][i]>=0的i就行了。
至于分组背包，我们设dp[i][u][j]表示以u为根的子树，仅用前i个儿子，满足j个客户取得最大价值，
那么dp[i][u][j]=max(dp[i-1][u][j-k]+dp[full_son_size[v]][v][k]);
而i这一维可以直接用滚动数组优化掉。
而这个背包，有些细节优化是可以过掉讨论中的那个极限数据。
如，将下面题解代码中sum+=x改到dp后。然后把dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])
改为dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k])，最后把dp[u][j]先用一个数组t保存一下就行了。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3010;
int n,m,EdgeCnt=0;
int dp[N][N],val[N],a[N],t[N];
struct Edge{
int to,w,next;
}e[N*N];
int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
void addedge(int u,int v,int w){
int p=++EdgeCnt;
e[p].to=v;e[p].w=w;e[p].next=a[u];
a[u]=p;
}
int dfs(int u){
if (u>n-m){
dp[u][1]=val[u];
return 1;
}
int sum=0;
for (int p=a[u];p;p=e[p].next){
int v=e[p].to;
int tk=dfs(v);
for (int j=0;j<=sum;j++)t[j]=dp[u][j];
for (int j=0;j<=sum;j++)
for (int k=0;k<=tk;k++)
dp[u][j+k]=max(dp[u][j+k],t[j]+dp[v][k]-e[p].w);
sum+=tk;
}
return sum;
}
int main(){
n=read(),m=read();
memset(dp,~0x3f,sizeof(dp));
for (int u=1;u<=n-m;u++){
int size=read();
for (int j=1;j<=size;j++){
int v=read(),w=read();
addedge(u,v,w);
}
}
for (int i=n-m+1;i<=n;i++)
val[i]=read();
for (int i=1;i<=n;i++)
dp[i][0]=0;
dfs(1);
for (int i=m;i>0;i--)
if (dp[1][i]>=0){
printf("%d",i);
break;
}
return 0;
}
优质内容筛选与推荐>>
1、谷歌终于推出TensorFlowLite，实现在移动设备端部署AI
2、机器学习（三）——k-近邻算法基础
3、027android初级篇之Intent相关介绍
4、ubuntu10.10安装openfetion
5、【追光者系列】HikariCP连接池监控指标实战