poj2486

题目大意：给出一个树，每个节点有一个值，问从1开始走走k步最多能遍历到最大的值的和；
dp[i][j][k] 当i为零是表示如果从j点开始遍历以j为跟的子树，走k步后回到原点的最大值。
dp[i][j][k] 当i为零是表示如果从j点开始遍历以j为跟的子树，走k步后不回到原点的最大值。

我们知道的是如果能走k步最大值为maxa那么走j>k步至少为maxa，所以每次用子树的和当前节点做背包，0+0= 0,0+1=1,1+0=1；

由于避免重复我是用了一个类似于滚动数组的东西处理的背包部分，但是我后来发现那样好蠢还不好写还费时其实将一类中的某一个放入背包中完全能将背包倒过来然后每到一格将所有的东西装进去就行了。

第一次的代码是这样的

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int maxa = ;

const int maxn = ;

int dp[][maxa][maxa];//0表示能回到当前位置，1表示不回到

int edge[maxa][maxa];

int vv[maxa];

int num[maxa];

int n, p;

int dp1[maxa];

//#define max(a,b) a>b?a:b

void dfs(int a, int fa){

    for(int i = ; i  < num[a]; i++){

        int k = edge[a][i];

        if(k != fa){

            dfs(k, a);

        }

    }

    for(int i = ; i <= p; i++)

        dp[][a][i] = dp[][a][i] = vv[a];

    for(int u = ; u < num[a]; u++){

        int v = edge[a][u];

        if(v != fa){

            for(int i = ; i <= p; i++)

                dp1[i] = vv[a];

            for(int i = ; i <= p; i++){

                for(int k = ; k <= p; k++){

                    if(i + k + <= p){

                        dp1[i+k+] = max(dp1[i+k+], dp[][a][i]+dp[][v][k]);

                    }

                    if(i+k+ <= p)

                        dp1[i+k+] = max(dp1[i+k+], dp[][a][i]+dp[][v][k]);

                }

            }

            for(int i =  ; i <= p; i++){

                dp[][a][i] = max(dp[][a][i], dp1[i]);

            }

            for(int i = ; i <= p; i++)

                dp1[i] = vv[a];

            for(int i = ; i <= p; i++){

                for(int k = ; k <= p; k++){

                    if(i+k+ <= p){

                        dp1[i+k+] = max(dp1[i+k+],dp[][a][i]+ dp[][v][k]);

                    }

                }

            }

            for(int i = ; i <= p; i++){

                dp[][a][i] = max(dp[][a][i],dp1[i]);

            }

        }

    }

}

int main(){

    while(scanf("%d%d", &n, &p)!=EOF){

        int a, b;

        memset(num, , sizeof(num));

        for(int i = ; i <= n; i++){

            scanf("%d", &vv[i]);

        }

        for(int i = ; i < n; i++){

            scanf("%d%d", &a, &b);

            edge[a][num[a]++] = b;

            edge[b][num[b]++] = a;

        }

        //memset(dp, 0, sizeof(dp));

        dfs(, );

        printf("%d\n", dp[][][p]);

    }

}

/*

8 6

1 1 1 1 1 1 1 4

1 2

1 3

1 4

1 5

1 6

1 7

1 8

*/

改后是这样的

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int maxa = ;

const int maxn = ;

int dp[][maxa][maxa];//0表示能回到当前位置，1表示不回到

int edge[maxa][maxa];

int vv[maxa];

int num[maxa];

int n, p;

//#define max(a,b) a>b?a:b

void dfs(int a, int fa){

    for(int i = ; i  < num[a]; i++){

        int k = edge[a][i];

        if(k != fa){

            dfs(k, a);

        }

    }

    for(int i = ; i <= p; i++)

        dp[][a][i] = dp[][a][i] = vv[a];

    for(int u = ; u < num[a]; u++){

        int v = edge[a][u];

        if(v != fa){

            for(int i = p; i >= ; i--){

                for(int k = ; k <= i; k++){

                    if(i - k-  >= ){

                        dp[][a][i] = max(dp[][a][i], dp[][a][k]+dp[][v][i-k-]);

                        dp[][a][i] = max(dp[][a][i], dp[][a][k]+dp[][v][i-k-]);

                    }if(i - k -  >= ){

                        dp[][a][i] = max(dp[][a][i], dp[][a][k]+dp[][v][i-k-]);

                    }

                }

            }

        }

    }

}

int main(){

    while(scanf("%d%d", &n, &p)!=EOF){

        int a, b;

        memset(num, , sizeof(num));

        for(int i = ; i <= n; i++){

            scanf("%d", &vv[i]);

        }

        for(int i = ; i < n; i++){

            scanf("%d%d", &a, &b);

            edge[a][num[a]++] = b;

            edge[b][num[b]++] = a;

        }

        //memset(dp, 0, sizeof(dp));

        dfs(, );

        printf("%d\n", max(dp[][][p], dp[][][p]));

    }

}

/*

8 6

1 1 1 1 1 1 1 4

1 2

1 3

1 4

1 5

1 6

1 7

1 8

*/

巴特西

poj2486

最新文章

热门文章