有线电视网 洛谷 - P1273

https://www.luogu.org/problemnew/show/P1273

只能想到n^3的办法 一看数据量自闭了。。 看了题解也是n^3 智障出题人

dp[i][j]代表以i为根的子树选j个用户时得到的最大收益 然后就是树上背包转移一下 最后看根节点上最多选几个人不亏本

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=0x3f3f3f3f;
const int maxn=3e3+10;
struct node
{
int v,next;
};
node edge[maxn];
int dp[maxn][maxn];
int first[maxn],pre[maxn],val[maxn],sum[maxn],tmp[maxn];
int n,m,num;
void addedge(int u,int v)
{
edge[num].v=v;
edge[num].next=first[u];
first[u]=num++;
}
void dfsI(int cur)
{
int i,v;
if(cur>n-m) sum[cur]=1;
for(i=first[cur];i!=-1;i=edge[i].next){
v=edge[i].v;
dfsI(v);
sum[cur]+=sum[v];
}
}
void dfsII(int cur)
{
int i,j,k,v;
dp[cur][0]=0;
if(cur>n-m) dp[cur][1]=val[cur];
for(i=first[cur];i!=-1;i=edge[i].next){
v=edge[i].v;
dfsII(v);
for(k=0;k<=sum[cur];k++) tmp[k]=dp[cur][k];
for(j=0;j<=sum[v];j++){
for(k=sum[cur];k>=j;k--){
tmp[k]=max(tmp[k],dp[cur][k-j]+dp[v][j]-pre[v]);
}
}
for(k=0;k<=sum[cur];k++) dp[cur][k]=tmp[k];
}
}
int main()
{
int k,i,j,v,t,ans;
scanf("%d%d",&n,&m);
memset(first,-1,sizeof(first));
num=0;
for(i=1;i<=n-m;i++){
scanf("%d",&k);
while(k--){
scanf("%d",&v);
scanf("%d",&pre[v]);
addedge(i,v);
}
}
for(i=n-m+1;i<=n;i++){
scanf("%d",&val[i]);
}
for(i=1;i<=n;i++){
for(j=0;j<=m;j++){
dp[i][j]=-N;
}
}
dfsI(1);
dfsII(1);
ans=0;
for(i=1;i<=m;i++){
if(dp[1][i]>=0) ans=i;
}
printf("%dn",ans);
return 0;
}

最后

以上就是无情蜻蜓为你收集整理的有线电视网 洛谷 - P1273的全部内容，希望文章能够帮你解决有线电视网 洛谷 - P1273所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。