总结
1. 这里 dp[][][] 不是恰好走 k 步, 而是最多走 k 步. 恰好和最多的区别就在于 dp 数组的初始化上了
代码
/* * source.cpp * * Created on: Apr 7, 2014 * Author: sangs */#include#include #include #include #include #include #include using namespace std;int val[1000];int dp[500][500][2];vector graph[1000];/* * dp[u][t][0] start from u and end at u, maximum income in t steps * dp[u][t][1] .............not end at u, maximum income in ....... * dp[u][t][0] = max(dp[u][t][0], dp[u][t-2-k][0] + dp[v][k][0]) v is child of u * dp[u][t][1] = max(dp[u][t][1], dp[u][t-1-k][0] + dp[v][k][1]) v is child of u and girl end at v * dp[u][t][1] = max(dp[u][t][1], dp[u][t-2-k][1] + dp[v][k][0]) v is child of u and girl end at another child of u */void solve_dp(int u, int pre, int vmax) { for(int i = 0; i <= vmax; i ++) // at most k steps, not exactly k steps dp[u][i][0] = dp[u][i][1] = val[u]; for(size_t i = 0; i < graph[u].size(); i ++) { int v = graph[u][i]; if(v == pre) continue; solve_dp(v, u, vmax); for(int j = vmax; j >= 0; j --) { for(int k = 0; k <= j; k ++) { dp[u][j+2][0] = max(dp[u][j][0], dp[u][j-k][0] + dp[v][k][0]); dp[u][j+1][1] = max(dp[u][j][1], dp[u][j-k][0] + dp[v][k][1]); dp[u][j+2][1] = max(dp[u][j][1], dp[u][j-k][1] + dp[v][k][0]); } } }}int main() { freopen("input.txt", "r", stdin); int n, T; while(scanf("%d%d", &n, &T) != EOF) { for(int i = 1; i <= n; i ++) scanf("%d", val+i); for(int i =1; i <= n; i ++) graph[i].clear(); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n-1; i ++) { int from, to; scanf("%d%d", &from, &to); graph[from].push_back(to); graph[to].push_back(from); } solve_dp(1, -1, T); cout << dp[1][T][1] << endl; } return 0;}