poj 1155 TELE

SubmitStatus

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

5

DP题，又一次深刻地感受到自己DP的弱。。。

题意：（摘自松AK）

给出一棵树，一共n个节点（根节点为电视台），其中有m个叶子结点（用户）依次为n-m+1~n。
接下来n行描述非叶子节点1~n，首先是一个k，表示它有k个子节点。接下来，每两个数描述一个节点的编号及与这个节点的距离（经过此路线的费用）。
最后一行n-m+1包括这些点（用户）拥有的钱数。
本题要求的是电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。

思路嘛，好多都讲得不是很清楚。

我们定义dp[i][j],  为以i为根节点，给j个用户发送信号所得到的最大剩余费用。

我们遍历一棵树时，按dfs顺序，一棵一棵子树地遍历, 算dp[i][j]时按一棵一棵子树去更新。比如到了u，遍历到它的子节点v, 那么dfs(v), 然后dp[u][j+k] = max(dp[u][j+k], dp[u][j]+dp[v][k]-d);  (d: u,v之间的路程) j与k分别是(0-size[u])与(0-size[v]), size[i]表示dfs到当前阶段时i的子节点个数，所以弄完v以后还有一句size[u] += size[v];

    初值叶子节点赋值就是了，还有一点注意是上面的dp[u][j]需要在前面弄一个t[]把dp[u][]存下来，再用t[]代替dp[u][],不然在算的时候会有覆盖现象。

//poj 1155 
//miaomiao_ymxl 2016.9.3
//
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define MAXN (3000+5)
#define INF 0x7f7f7f7f

struct node{
    int v, dis;
};

vector<node> G[MAXN];
int size[MAXN], dp[MAXN][MAXN], t[MAXN];

void dfs(int u){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i].v, d = G[u][i].dis;
        dfs(v);
        
        for(int j = 0; j <= size[u]; j++) t[j] = dp[u][j];
        for(int j = 0; j <= size[u]; j++)
          for(int k = 0; k <= size[v]; k++)
            dp[u][j+k] = max(dp[u][j+k], dp[v][k]+t[j]-d);
        
        size[u] += size[v];
    }
}

int main(){
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    
    int n, m;
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++) dp[i][j] = -INF;
    
    for(int i = 1; i <= (n-m); i++){
        int ni;
        scanf("%d", &ni);
        
        for(int j = 1; j <= ni; j++){
            int v, dis;
            scanf("%d%d", &v, &dis);
            
            G[i].push_back((node){v, dis});
        }
    }
    
    for(int i = (n-m+1); i <= n; i++){
        int x;
        scanf("%d", &x);
        
        dp[i][1] = x;
        size[i] = 1;
    }
    
    dfs(1);
    for(int i = n; i; i--)
        if(dp[1][i] >= 0){
            printf("%dn", i);
            break;
        } 
    
    return 0;
}

最后

以上就是飘逸翅膀为你收集整理的poj 1155 TELE的全部内容，希望文章能够帮你解决poj 1155 TELE所遇到的程序开发问题。

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