本文共 1678 字，大约阅读时间需要 5 分钟。

1、

2、题目大意：

有n台电视，其中这n台电视中有n-m台是服务器，有m台式用户，现在已知每条线路的代价值，又知道每个用户想给服务器的钱数，在电视台不亏损的前提下，最多可以让多少用户接收到信号

分析：

这是一道树形DP的问题，首先定义状态dp[i][j]表示以i为根节点j个用户的最大收益

那么我们要求最多的用户数，只要在i={0-m}个用户个数中，找到使得dp[1][i]>=0的这个i值即可

假设fa是当前的父节点，v是fa的子节点，那么dp[fa][j]=max(d[fa][j],dp[fa][j-k]+dp[v][k]-w[fa][v])

以fa为根节点的j个用户的最大收益就等于以fa的子节点为根的k个再加上以fa为根的j-k个和

-w[i][j]是因为当前选中fa的子节点v，那么fa到v的这条边就得加上，只不过这是电视台的消费，所以为负值

另外需要一个tmp[j]数组来记录dp[fa][j],优化

3、AC代码

#include
   
    #include
    
     #include
     
      using namespace std;#define N 3005#define INF 0x7fffffffint v[N];int w[N];int head[N];int next[N];int tot=0;int dp[N][N];int num[N];int tmp[N];void add_edge(int a,int b,int c){    v[tot]=b;    w[tot]=c;    next[tot]=head[a];    head[a]=tot++;}void dfs(int fa){    for(int i=head[fa];i!=-1;i=next[i])    {        int vv=v[i];        dfs(vv);        for(int j=0;j<=num[fa];j++)        tmp[j]=dp[fa][j];        for(int j=0;j<=num[fa];j++)        {            for(int k=1;k<=num[vv];k++)            {                dp[fa][j+k]=max(dp[fa][j+k],tmp[j]+dp[vv][k]-w[i]);            }        }        num[fa]+=num[vv];    }}int main(){    int n,m,k,a,b;    scanf("%d%d",&n,&m);    memset(head,-1,sizeof(head));    for(int i=1;i<=n-m;i++)    {        num[i]=0;        scanf("%d",&k);        for(int j=1;j<=k;j++)        {            scanf("%d%d",&a,&b);            add_edge(i,a,b);        }    }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        dp[i][j]=-INF;    }    for(int i=n-m+1;i<=n;i++)    {        scanf("%d",&dp[i][1]);        num[i]=1;    }    dfs(1);    for(int i=m;i>=0;i--)    {        if(dp[1][i]>=0)        {             printf("%d\n",i);             break;        }    }    return 0;}
     
    
   

转载地址：http://srddi.baihongyu.com/