洛谷 偷天换日&&“访问”美术馆

典型的树形DP

按理说是先做“访问美术馆”再做偷天换日。

但是我先做了偷天换日然后再做的“访问”美术馆

DP方程好推,偷天换日在遇到有展品的时候做背包,因为是先做的偷天换日,所以把偷天换日的输入w,c直接将输入改为赋值就A了。

洛谷 偷天换日&&“访问”美术馆

洛谷 偷天换日&&“访问”美术馆

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 311
using namespace std;
struct node{
int to, nxt, val;
}edge[MAXN << ];
int flag, tot, n, head[MAXN], nxt[MAXN << ], to[MAXN << ], w[MAXN], val[MAXN << ], dp[MAXN][MAXN << ];
void add(int u, int v, int w) {
edge[++tot].nxt = head[u], head[u] = tot, edge[tot].to = v, edge[tot].val = w;
edge[++tot].nxt = head[v], head[v] = tot, edge[tot].to = u, edge[tot].val = w;
}
void dfs(int now) {
int t, x, flag1;
scanf("%d%d", &t, &x);
add(now, ++flag, t << );
if(!x) flag1 = flag, dfs(flag1), dfs(flag1);
else for(int i = , c, w; i <= x; i++) {
scanf("%d%d", &w, &c);
// w = 1, c = 5;
for(int j = n; j >= c; j--) dp[flag][j] = max(dp[flag][j], dp[flag][j - c] + w);
}
}
void dfs1(int now, int fa) {
for(int i = head[now]; i; i = edge[i].nxt)
if(fa != edge[i].to) {
dfs1(edge[i].to, now);
for(int j = n; j >= ; j--)
for(int k = edge[i].val; k <= j; k++)
dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[edge[i].to][k - edge[i].val]);
}
}
int main() {
scanf("%d", &n), n--;
dfs(++flag);
dfs1(, );
printf("%d", dp[][n]);
return ;
}

洛谷 偷天换日&&“访问”美术馆

洛谷 偷天换日&&“访问”美术馆

洛谷 偷天换日&&“访问”美术馆

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 311
using namespace std;
struct node{
int to, nxt, val;
}edge[MAXN << ];
int flag, tot, n, head[MAXN], nxt[MAXN << ], to[MAXN << ], w[MAXN], val[MAXN << ], dp[MAXN][MAXN << ];
void add(int u, int v, int w) {
edge[++tot].nxt = head[u], head[u] = tot, edge[tot].to = v, edge[tot].val = w;
edge[++tot].nxt = head[v], head[v] = tot, edge[tot].to = u, edge[tot].val = w;
}
void dfs(int now) {
int t, x, flag1;
scanf("%d%d", &t, &x);
add(now, ++flag, t << );
if(!x) flag1 = flag, dfs(flag1), dfs(flag1);
else for(int i = , c, w; i <= x; i++) {
// scanf("%d%d", &w, &c);
w = , c = ;
for(int j = n; j >= c; j--) dp[flag][j] = max(dp[flag][j], dp[flag][j - c] + w);
}
}
void dfs1(int now, int fa) {
for(int i = head[now]; i; i = edge[i].nxt)
if(fa != edge[i].to) {
dfs1(edge[i].to, now);
for(int j = n; j >= ; j--)
for(int k = edge[i].val; k <= j; k++)
dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[edge[i].to][k - edge[i].val]);
}
}
int main() {
scanf("%d", &n), n--;
dfs(++flag);
dfs1(, );
printf("%d", dp[][n]);
return ;
}

一世安宁

上一篇:如何架设部署V2EX社区/论坛(Google App Engine版)


下一篇:洛谷 P1270 “访问”美术馆 解题报告