Binary Apple Tree(ツリーdp)

4423 ワード

アルゴリズム

タイトルリンク:https://cn.vjudge.net/contest/252252#problem/C
日语翻译:...
2つの解法を与えました.1 ms走ったのと15 ms走ったのとで、どちらもこの問題を乗り越えることができますが、なぜ速さと遅さの差がこんなに大きいのか、とても考える価値があります.
1つ目(dfsエッジ更新dp):

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define MOD 1000000007
#define INF 0x3fffffff
#define mod(x) (x%MOD)
#define CLR(a,x) memset(a,x,sizeof(a))
#define FILL(a,n,x) fill(a,a+n,x)
#define WHILE() int T;scanf("%d",&T);while(T--)
#define rep( i, l, r ) for( int i = l; i <= r; ++i )
#define pre( i, r, l ) for( int i = r; i >= l; --i )
#define mod(x) (x%MOD)
#define FILL(a,n,x)  fill(a,a+n,x)
const double PI = acos(-1.0);

const int maxn = 210;

int n,q,tot;
int head[maxn], sizen[maxn];
int dp[maxn][maxn];

struct node
{
    int next;
    int to;
    int w;
    node(){}
    node(int _next, int _to, int _w):next(_next), to(_to), w(_w){}
}edge[maxn];

void add(int u, int v, int w)
{
    edge[tot] = node(head[u],v,w);
    head[u] = tot ++;
}

void dfs(int u, int f)
{
    sizen[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v == f) continue;
        dfs(v,u);
        sizen[u] += sizen[v];
        for(int j = sizen[u]; j > 1; j --){
            for(int k = min(sizen[v], j-1); k >= 1; k --){
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k] + edge[i].w);
            }
        }
    }
}

int main()
{
    //freopen("DATA.c", "r", stdin);
    ios::sync_with_stdio(false); cin.tie();cout.tie();
    while(~scanf("%d%d", &n, &q)){
        tot = 0;
        int u,v,w;
        memset(head,-1,sizeof(head));
        for(int i = 1; i < n; i ++){
            scanf("%d%d%d", &u, &v, &w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,-1);
        printf("%d
", dp[1][q+1]);
    }
    return 0;
}

2つ目は、(まずdfsがすべてのノードをプレイし、各ノードがルートであるサブツリーのサイズ(ルートを含む)を算出した後、dp更新する.これは、サブノードが親ノードを更新する際に、親ノードが表すサブツリーが非常に大きいため、更新の代価が非常に大きく、明らかに冗長である)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define MOD 1000000007
#define INF 0x3fffffff
#define mod(x) (x%MOD)
#define CLR(a,x) memset(a,x,sizeof(a))
#define FILL(a,n,x) fill(a,a+n,x)
#define WHILE() int T;scanf("%d",&T);while(T--)
#define rep( i, l, r ) for( int i = l; i <= r; ++i )
#define pre( i, r, l ) for( int i = r; i >= l; --i )
#define mod(x) (x%MOD)
#define FILL(a,n,x)  fill(a,a+n,x)
const double PI = acos(-1.0);

const int maxn = 210;

int n,q,tot;
int head[maxn], sizen[maxn];
int dp[maxn][maxn];

struct node
{
    int next;
    int to;
    int w;
    node(){}
    node(int _next, int _to, int _w):next(_next), to(_to), w(_w){}
}edge[maxn];

void add(int u, int v, int w)
{
    edge[tot] = node(head[u],v,w);
    head[u] = tot ++;
}

void dfs(int u, int f)
{
    sizen[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v == f) continue;
        dfs(v,u);
        sizen[u] += sizen[v];
    }
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v == f) continue;
        for(int j = sizen[u]; j > 1; j --){
            for(int k = min(sizen[v], j-1); k >= 1; k --){
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k] + edge[i].w);
            }
        }
    }
}

int main()
{
    //freopen("DATA.c", "r", stdin);
    ios::sync_with_stdio(false); cin.tie();cout.tie();
    while(~scanf("%d%d", &n, &q)){
        tot = 0;
        int u,v,w;
        memset(head,-1,sizeof(head));
        for(int i = 1; i < n; i ++){
            scanf("%d%d%d", &u, &v, &w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,-1);
        printf("%d
", dp[1][q+1]);
    }
    return 0;
}

Java 8のデフォルトメソッド

Photoshopの関連付けがうまくいかないのを直す(Windows)