Placing Lampposts
题目传送:UVA - 10859 - Placing Lampposts
巧妙的思想:
对于有两个需要优化的量v1和v2的时候,要求首先满足v1最小,在v1相同的情况下v2最小,则这里可以把二者组合成一个量M*v1+v2,其中M是一个比”v2的最大理论值和v2的最小理论值之差”还要大的数。
AC代码:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;
vector<int> G[];
int vis[][], d[][];
int n, m;
int dp(int i, int j, int f) {
if(vis[i][j]) return d[i][j];
vis[i][j] = ;
int& ans = d[i][j];
ans = ;
for(int k = ; k < G[i].size(); k ++) {
if(G[i][k] != f) {
ans += dp(G[i][k], , i);
}
}
if(f >= && !j) ans ++;
if(j || f < ) {
int sum = ;
for(int k = ; k < G[i].size(); k ++) {
if(G[i][k] != f) {
sum += dp(G[i][k], , i);
}
}
if(f >= ) sum ++;
ans = min(ans, sum);
}
return ans;
}
int main() {
int T;
scanf("%d", &T);
while(T --) {
scanf("%d %d", &n, &m);
for(int i = ; i < n; i ++) G[i].clear();
int a, b;
for(int i = ; i < m; i ++) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
memset(d, , sizeof(d));
memset(vis, , sizeof(vis));
int ans = ;
for(int i = ; i < n; i ++) {
if(!vis[i][]) {
ans += dp(i, , -);
}
}
printf("%d %d %d\n", ans / , m - ans % , ans % );
}
return ;
}
刷油漆
题目传送:hihoCoder - 1055 - 刷油漆
昨天第一次做树形DP的题,感觉很神奇!思想甚是巧妙!
今天这个树形DP是类似背包的一个题,因为递推方程差不多
不过要注意一点,枚举每一个子树的那一层循环只能放最外面
因为:
如果把枚举每一个子树放到最内层,枚举”背包容量”放到最外面一层,则这样会产生最优解没有及时更新到最外面那一层的情况,导致出错。比如n=INF,m=9,根结点取1(因为必须取根节点),他有很多子树,而取其中两个子树3个结点和5个节点为最优解。当取第二个子树5个结点时,因为dp[1][4](即第一个子树的3个结点对应的应该已经更新的位置)还没更新(因为是倒序枚举m),此时得不到最优解。
AC代码:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;
const int maxn = ;
int dp[][];//dp[i][j]表示在以i为根的一棵树中,选出包含根节点i的j个连通的结点,能够获得的最高的评分,然后我们的答案就是dp[1][m].
int n, m;
vector<int> G[maxn];
void dfs(int u, int fa) {
int d = G[u].size();
for(int i = ; i < d; i ++) {
if(G[u][i] != fa) dfs(G[u][i], u);
}
for(int k = ; k < d; k ++) {//枚举每一个子节点,这里必须把枚举每一个子节点放在外面,因为可能在遍历完这个子树之后,再遍历另一个子树可能会得到最优解,而每次只枚举每个子树的一部分得不到最优解
int v = G[u][k];
if(v != fa)
for(int j = m; j >= ; j --) {//倒序枚举刷油漆的数量,类似背包
for(int i = ; i < j; i ++) {
dp[u][j] = max(dp[u][j], dp[u][j - i] + dp[v][i]);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i ++) {
scanf("%d", &dp[i][]);
}
int u, v;
for(int i = ; i < n; i ++) {
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, -);
printf("%d\n", dp[][m]);
return ;
}