pku 1463?Strategic game

http://poj.org/problem?id=1463

題意：

給定一個樹，求在節點上放士兵來檢查所有的線路。當i節點有士兵的時候，與i節點相連接的線路都可以被檢測了。求所需的最少的士兵。

思路：
dp[i][0]表示i節點不放士兵，dp[i][1]表示i節點放士兵，

dp[i][0] += dp[j][1] j是i的子節點 若果i節點未放士兵，則它的子節點必須放士兵

dp[i][1] += min(dp[j][0],dp[j][1]) j是i的子節點 若i節點放了士兵，則它的子節點可放可不放。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 10007 #define N 1507 using namespace std; //freopen("din.txt","r",stdin);int dp[N][2]; vector<int>vc[N];void dfs(int u,int pa){int len = vc[u].size();for (int i = 0; i < len; ++i){int v = vc[u][i];if (v == pa) continue;dfs(v,u);//printf(">>>>%d %d\n",u,v);dp[u][1] += min(dp[v][0],dp[v][1]);dp[u][0] += dp[v][1];} } int main(){//freopen("din.txt","r",stdin);int i,j;int n;int s,e,num;while (~scanf("%d",&n)){for (i = 0; i < n; ++i) vc[i].clear();for (i = 0; i < n; ++i){scanf("%d:(%d)",&s,&num);for (j = 0; j < num; ++j){scanf("%d",&e);vc[s].push_back(e);vc[e].push_back(s);}}for (i = 0; i < n; ++i){dp[i][0] = 0;dp[i][1] = 1;}dfs(0,-1);/*for (i = 0; i < n; ++i){printf("%d %d\n",dp[i][0],dp[i][1]);}*/printf("%d\n",min(dp[0][0],dp[0][1]));}return 0; }

zoj?Treasure Hunt I ?樹上背包。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4772

題意:

題意：

給定n個點n-1條邊，每個點對應一個財富值，走每條路徑都對應著一個所需要的時間，問在m天內從k出發然后回到k，所能取得到的最大財富值 路徑為k,v1 V2 ....v1,k.

思路：
原來做過的題目，拿過還是沒有想全面，沒能很好的理解，看來做的這類題目還是少啊。首先題意是給定一棵樹，必須按原路返回，所以每條路徑走兩次，也就是花費2*w才能走子節點。

dp[u][j] = max(dp[u][j],dp[u][j - c - k] + dp[v][k]); ?u為父節點，v為子節點，這里相當于把每個節點分成了m個狀態，我們只能從這m個狀態里面選擇一個或者不選，于是就構成了分組背包類型。 dp[v][k]表示子節點v在k狀態時的w值，而k則對應了c值。（這里c,w為背包講解里的c,w）.

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 2007 #define N 107 using namespace std; //freopen("din.txt","r",stdin);struct node{int v,w;int next; }g[M]; int head[N],ct;int dp[N][M]; int val[N]; int m; bool vt[N];void add(int u,int v,int w){g[ct].v = v;g[ct].w = w;g[ct].next = head[u];head[u] = ct++; } void dfs(int u){int i,j,k;for (i = head[u]; i != -1; i = g[i].next){int v = g[i].v;printf("%d %d\n",u,v);if (vt[v]) continue;int c = g[i].w*2;dfs(v);for (j = m; j >= c; --j){for (k = 0; k <= j - c; ++k)dp[u][j] = max(dp[u][j],dp[u][j - c - k] + dp[v][k]);}}for (i = 0; i <= m; ++i) dp[u][i] += val[u]; } int main(){//freopen("din.txt","r",stdin);int i;int n,k;int x,y,z;while (~scanf("%d",&n)){ct = 0; CL(head,-1); CL(vt,false);for (i = 1; i <= n; ++i) scanf("%d",&val[i]);for (i = 1; i < n; ++i){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}CL(dp,0);scanf("%d%d",&k,&m);dfs(k);printf("%d\n",dp[k][m]);}return 0; }

?

hdu ?The Ghost Blows Light 樹上背包+spfa處理

http://acm.hdu.edu.cn/showproblem.php?pid=4276‘

題意：

給定n個點n-1條邊，每個點對應一個財富值，走每條路徑都對應著一個所需要的時間，問在T天內從1出發到N做能取得的最大財富值。

思路：

這題是上邊那道題目的加強版，首先我們如果用樹上的分組背包做的話，每個路徑的話費必須是確定的，而我們這里確實不確定的，可以直接走一次，也可以來回走兩次。所以才開始想的時候真的沒想到要用spfa處理，我們用spfa求最短路徑，記錄路徑，我們在走的時候肯定會走最短路來選擇（因為給定的是一棵樹，從1到n只存在一條路徑，所以必走）。然后將他們的w置為0，這樣我們就能保證最短路徑必選了，然后再用2*w的c去檢查非最短路徑上，最后套用上邊的那個背包就好了。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 507 #define N 107 using namespace std; //freopen("din.txt","r",stdin);struct node{int v,w;int next; }g[N*2]; int head[N],ct;int dp[N][M],val[N]; int dis[N],pre[N],path[N]; bool vt[N]; int n,T;void add(int u,int v,int w){g[ct].v = v;g[ct].w = w;g[ct].next = head[u];head[u] = ct++; } void spfa(int s){int i;for (i = 1; i <= n; ++i){vt[i] = false;dis[i] = inf;pre[i] = -1; path[i] = -1;}dis[s] = 0;queue<int>q;q.push(s); vt[s] = true;while (!q.empty()){int u = q.front(); q.pop();for (i = head[u]; i != -1; i = g[i].next){int v = g[i].v;int w = g[i].w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;pre[v] = u;path[v] = i;if (!vt[v]){vt[v] = true;q.push(v);}}}vt[u] = false;}for (i = n; i != s; i = pre[i]){g[path[i]].w = 0;g[path[i]^1].w = 0;} } void dfs(int u){vt[u] = true;int i,j,k;for (i = head[u]; i != -1; i = g[i].next){int v = g[i].v;if (vt[v]) continue;int c = g[i].w*2;dfs(v);for (j = T; j >= c; --j){for (k = 0; k <= j - c; ++k){dp[u][j] = max(dp[u][j],dp[u][j - c - k] + dp[v][k]);}}}for (i = 0; i <= T; ++i) dp[u][i] += val[u]; } int main(){// freopen("din.txt","r",stdin);int i;int x,y,z;while (~scanf("%d%d",&n,&T)){ct = 0; CL(head,-1);for (i = 1; i < n; ++i){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}for (i = 1; i <= n; ++i) scanf("%d",&val[i]);spfa(1);if (dis[n] > T){puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");continue;}T -= dis[n];CL(dp,0); CL(vt,false);dfs(1);printf("%d\n",dp[1][T]);}return 0; }

?

?

待更新......

轉載于:https://www.cnblogs.com/E-star/archive/2012/10/13/2722706.html

總結

以上是生活随笔為你收集整理的树形DP题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。