没有上司的舞会
树可以DP的天然优势就是子树自成一个子问题，只考虑在节点处合并即可。
\(f[i][0]\)表示这个点不选择
\(f[i][1]\)表示这个点选择
代码：
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 6000 + 7;
vector<int> g[maxN];
int a[maxN];
int f[maxN][2];
bool vis[maxN];
void dfs(int now) {
f[now][1] = a[now];
for(int i = 0;i < g[now].size();++ i) {
int v = g[now][i];
dfs(v);
f[now][1] += f[v][0];
f[now][0] += max(f[v][1] , f[v][0]);
}
}
int main() {
int n = gi();
rep(i , 1, n) a[i] = gi();
rep(i , 1, n - 1) {
int v = gi(),u = gi();
g[u].push_back(v);
vis[v] = true;
}
int root;
rep(i , 1, n) if(!vis[i]) root = i;
dfs(root);
printf("%d",max(f[root][0] , f[root][1]));
return 0;
}
P2607 骑士
士兵关系可以形成一张基环森林。
考虑断环上的一边，对顶点（u,v）分别树形DP
\(f[i][0]\)表示这个点不选择
\(f[i][1]\)表示这个点选择
\(f[i][1] = \sum_{v \in son_i}f[v][0]\)
\(f[i][0] = \sum_{v \in son_i}max(f[v][0],f[v][1])\)
那么答案是max(f[u][0],f[v][0])
因为u跟v中必定有一个不选择。
还有一个问题就是为什么不枚举环上的所有边进行断边。
因为我们记录的答案已经含有所以可能的答案
没调过的代码：
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 1e6 + 7;
struct Node {
int v , nex;
}Map[maxN << 1];
int head[maxN] , num;
bool vis[maxN];
int a[maxN];
void add_Node(int u , int v) {
Map[++ num] = (Node) {v , head[u]};
head[u] = num;
}
int f[maxN][2];
bool cvis[maxN], vis2[maxN];
void find(int now , int fa) {
vis[now] = true;
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
if(vis[v]) {
cvis[now] = true;
return;
}
find(v , now);
if(cvis[v]) cvis[now] = true;
}
return ;
}
void dp(int now,int be,int end) {
vis2[now] = true;
f[now][1] = a[now];
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(now == be && v == end) continue;
if(now == end && v == be) continue;
if(vis2[v]) continue;
dp(v , be, end);
f[now][1] += f[v][0];
f[now][0] += max(f[v][0] , f[v][1]);
}
return ;
}
int main() {
int n = gi();
rep(i , 1, n) {
a[i] = gi();int x = gi();
add_Node(i , x);
add_Node(x , i);
}
int ans = 0;
rep(i , 1, n) {
if(!vis2[i]) {
int x , y;
find(i,0);
for(int j = i;j >= 1;-- j) {
if(vis2[j]) break;
if(cvis[j]) {
for(int now = head[j];now;now = Map[now].nex) {
int v = Map[now].v;
if(cvis[v]) {
x = j;y = v;
break;
}
}
}
}
memset(f , 0, sizeof(f));
dp(x , x, y);
memset(vis2,0,sizeof(vis2));
memset(f , 0, sizeof(f));
dp(y , x, y);
ans += max(f[x][0] , f[y][0]);
}
}
printf("%d",ans);
return 0;
}
P1131 时态同步
f(x) 表示让 x 子树内的叶子到 x 的距离相同，至少要多少次操作。
g(x) 表示 x 子树内的叶子到 x 的最长距离。
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define ll long long
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 5e5 + 7;
struct Node {
int v , nex, w;
}Map[maxN << 1];
int head[maxN] , num;
void add_Node(int u , int v, int w) {
Map[++ num] = (Node) {v , head[u], w};
head[u] = num;
}
ll f[maxN] , g[maxN];
void dfs(int now , int fa) {
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
dfs(v , now);
g[now] = max(g[v] + Map[i].w , g[now]);
}
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
f[now] += f[v] + (g[now] - g[v] - Map[i].w);
}
return ;
}
int main() {
int n = gi();
int root = gi();
for(int i = 1;i < n;++ i) {
int u = gi(),v = gi(),w = gi();
add_Node(u , v, w);
add_Node(v , u, w);
}
dfs(root , 0);
printf("%lld",f[root]);
return 0;
}
POI2017 Sabota (BZOJ4726)
考虑叛徒一定是在叶子结点，叛徒一定是一颗子树的全部结点。
const int maxN = 500000 + 7;
double f[maxN];
int siz[maxN];
vector<int> g[maxN];
void dfs(int now) {
siz[now] = 1;
for(int i = 0;i < g[now].size();++ i) {
int v = g[now][i];
dfs(v);
siz[now] += siz[v];
}
for(int i = 0;i < g[now].size();++ i) {
int v = g[now][i];
f[now] = max(f[now] , min(f[v] , 1.0 * siz[v] / (siz[now] - 1)));
}
if(siz[now] == 1) f[now] = 1;
}
int main() {
int n = gi() , k = gi();
for(int i = 1;i < n;++ i) {
int x = gi();
g[x].push_back(i + 1);
}
dfs(1);
double ans = 0;
for(int i = 1;i <= n;++ i) {
if(siz[i] > k) ans = max(ans , f[i]);
}
printf("%.10lf",ans);
return 0;
}
P4163 [SCOI2007]排列
状态压缩DP
\(f[S][i]\)表示S状态%d = i的方案数
转移枚举新添加的一位是什么
但这样是不对的，还要去重
再除以每一个数个数阶乘
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define int long long
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 12;
const int maxS = 1030;
char s[maxN];
int d,a[maxN],f[maxS][1007], cnt[10], fac[maxN], n;
void Read() {
scanf("%s%lld",s + 1,&d);
}
void Pre() {
fac[0] = 1;
rep(i , 1, 10) fac[i] = fac[i - 1] * i;
n = strlen(s + 1);
rep(i , 1, n) a[i] = s[i] - '0';
memset(cnt , 0, sizeof(cnt));memset(f , 0, sizeof(f));
rep(i , 1, n) cnt[a[i]] ++;
f[0][0] = 1;
}
void Solve() {
for(int S = 1;S < (1 << n);++ S) {
for(int i = 1;i <= n;++ i) {
if(S & (1 << i - 1)) {
int S1 = S ^ (1 << i - 1);
for(int j = 0;j < d;++ j) {
f[S][(j * 10 + a[i]) % d] += f[S1][j];
}
}
}
}
int& ans = f[(1 << n) - 1][0];
rep(i , 0, 9) ans /= fac[cnt[i]];
printf("%lld\n",ans);
}
signed main() {
int T = gi();
while(T --) {
Read();
Pre();
Solve();
}
return 0;
}
nmd，还有这么多题
COCI2009 podjela (BZOJ3090)
P3479 救火站
P2831 愤怒的小鸟
P3959 宝藏
P2157 学校食堂
ARC078 F
P2657 windy数
P3413 萌数
CF 914C
CF 834E
P1725
P3572 Little bird
P3177 树上染色
P5369 最大前缀和
P3226 集合选数
WF2017 Posteri
MiningGoldHard
AGC015 E