3 个 DP，还想了几道题，但不会。
*P3349 [ZJOI2016] 小星星
考虑树上的点最终会对应在图上的哪个点，设 \(f_{x,i}\) 表示树上的点 \(x\) 对应图上点 \(i\) 时的方案数，当 \(x\) 对应 \(i\) 后，在树上 \(x\) 的所有子节点也必须像在树上一样，在图上和 \(i\) 之间有连边，有了这条限制，可以写出状态转移方程 \(f_{x,i} = \prod_{y\in\text{son}(x)}\sum_{j=1}^n f_{y,j}\times g_{i,j}\)，其中 \(g\) 是图的邻接矩阵。
做到这里发现可能会有算重的部分，也就是说，树上有些点映射到图上的同一个点了，但是不要急着放弃，这个重复其实可以容斥掉！枚举所有点集合的子集 \(S\)，然后强制只能映射到图上的这些点中。\(\text{popcount}(S)=n\) 时加答案，\(\text{popcount}(S)=n-1\) 的时候扣掉……以此类推。时间复杂度 \(\mathcal{O}(n^32^n)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 20;
int n,m;
int g[N][N],_g[N][N];
vector<int> G[N];
long long ans, f[N][N];
void dfs(int x,int fa){
for (int i = 1;i <= n;i++) f[x][i] = 1;
for (int y : G[x]){
if (y == fa) continue;
dfs(y,x);
for (int i = 1;i <= n;i++){
long long sum = 0;
for (int j = 1;j <= n;j++)
sum += 1ll * f[y][j] * g[i][j];
f[x][i] *= sum;
}
}
}
signed main(){
cin >> n >> m;
for (int i = 1;i <= m;i++){
int x,y; cin >> x >> y;
g[x][y] = g[y][x] = 1;
_g[x][y] = _g[y][x] = 1;
}
for (int i = 1;i < n;i++){
int x,y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int S = 1;S < (1 << n);S++){
memset(f,0,sizeof(f));
for (int i = 1;i <= n;i++){
if (!(S & (1 << (i - 1)))){
for (int j = 1;j <= n;j++)
g[i][j] = g[j][i] = 0;
}
}
dfs(1,0);
long long res = 0;
for (int i = 1;i <= n;i++){
if (S & (1 << (i - 1))){
res += f[1][i];
}
}
if (__builtin_popcount((1 << n) - S - 1) & 1)
ans -= res;
else ans += res;
memcpy(g,_g,sizeof(g));
}
cout << ans;
return 0;
}
P6419 [COCI2014-2015#1] Kamp
很恶心的换根 DP！注意到点 \(i\) 最终的答案是，\(i\) 到所有关键点路径并 \(\times2\) 然后扣去与所有关键点里最大的那个的距离。到这里其实就做完了，细节非常多！求子树外最远距离需要记录次大值这是经典套路，求路径并的时候，要讨论子树内子树外是否有关键点的情况，在代码中标注出来了。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int n,k,f[N],g[N],_g[N],h[N],_h[N],cnt[N]; bool v[N];
struct Edge { int y,z; };
vector<Edge> G[N];
void dfs(int x,int fa){
if (v[x]) cnt[x]++;
for (auto e : G[x]){
int y = e.y, z = e.z;
if (y == fa) continue;
dfs(y,x);
cnt[x] += cnt[y];
if (cnt[y]) // !
f[x] += z + f[y];
if (cnt[y]){
if (g[y] + z > g[x]){
h[x] = g[x]; _h[x] = _g[x];
g[x] = g[y] + z; _g[x] = y;
}
else if (g[y] + z == g[x]){
h[x] = g[y] + z; _h[x] = y;
}
else if (g[y] + z > h[x]){
h[x] = g[y] + z; _h[x] = y;
}
}
}
}
void dfs2(int x,int fa){
for (auto e : G[x]){
int y = e.y, z = e.z;
if (y == fa){
if (k - cnt[x] == 0) continue; // !
f[x] = f[y];
if (cnt[x] == 0) f[x] += z; // !
if (_g[y] == x){
if (h[y] + z > g[x])
g[x] = h[y] + z, _g[x] = y;
else if (h[y] + z == g[x])
h[x] = h[y] + z, _h[x] = y;
else if (h[y] + z > h[x])
h[x] = h[y] + z, _h[x] = y;
}
else{
if (g[y] + z > g[x])
g[x] = g[y] + z, _g[x] = y;
else if (g[y] + z == g[x])
h[x] = g[y] + z, _h[x] = y;
else if (g[y] + z > h[x])
h[x] = g[y] + z, _h[x] = y;
}
continue;
}
}
for (auto e : G[x]){
int y = e.y, z = e.z;
if (y == fa) continue;
dfs2(y,x);
}
}
signed main(){
cin >> n >> k;
for (int i = 1;i < n;i++){
int x,y,z; cin >> x >> y >> z;
G[x].push_back({y,z}), G[y].push_back({x,z});
}
for (int i = 1;i <= k;i++){
int x; cin >> x;
v[x] = 1;
}
dfs(1,0);
dfs2(1,0);
for (int i = 1;i <= n;i++)
cout << f[i] * 2 - g[i] << '\n';
return 0;
}
**[ARC108E] Random IS
思考的时候从思维固化了，一直从顺序 DP 的角度去思考，然后就爆了啊。如果固定住一个区间 \([l,r]\)，那么区间外不管怎么选择，都不会影响到区间内的信息。那就可以考虑区间 DP。设 \(f_{l,r}\) 表示必须选 \(a_l,a_r\)，区间 \([l,r]\) 内标记个数的期望，区间 \((l,r)\) 内有 \(cnt\) 个不错的。转移直接枚举中间点 \(k\)，\(f_{l,r}=\dfrac{1}{k}\sum_{l<k<r,a_l < a_k < a_r}f_{l,k}+f_{k,r}+1\)。
这样时间复杂度是 \(O(n^3)\) 的，发现枚举过程中，\(l<k<r,a_l<a_k<a_r\) 是一个二维数点问题，于是可以固定下标，用权值树状数组求解，每次更新加入 \(f_{l,r}\) 即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, P = 1e9 + 7;
// #define int long long
int n,a[N];
struct SZSZ{
int c[N];
void add(int x,int y){
for (;x < N;x += x & -x) (c[x] += y) %= P;
}
int sum(int x){
int y = 0;
for (;x;x -= x & -x) (y += c[x]) %= P;
return y;
}
int query(int l,int r){
return (sum(r) - sum(l - 1) + P) % P;
}
}t[N][3];
int qpow(int a,int b){
int c = 1;
for (;b;b >>= 1,a = 1ll * a * a % P)
if (b & 1)
c = 1ll * c * a % P;
return c;
}
long long f[N][N];
signed main(){
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i], a[i]++;
a[0] = 1, a[n + 1] = n + 2;
for (int l = n;l >= 0;l--){
for (int r = l + 1;r <= n + 1;r++){
if (a[l] > a[r]) continue;
int cnt = t[l][2].query(a[l] + 1,a[r] - 1);
if (cnt)
f[l][r] = 1ll * (t[l][0].query(a[l] + 1,a[r] - 1) + t[r][1].query(a[l] + 1,a[r] - 1)) * qpow(cnt,P - 2) % P + 1;
t[l][2].add(a[r],1), t[l][0].add(a[r],f[l][r]), t[r][1].add(a[l],f[l][r]);
}
}
cout << f[0][n + 1];
return 0;
}
*\(\color{red}{\text{[ARC184D] Erase Balls 2D}}\)
想了很久还是不会。
*\(\color{red}{\text{CF708E Student's Camp}}\)
想到了和一篇题解类似的做法，但只会用一次的前缀和优化，再往后晕了，先咕着明天写。
标签：cnt,记录,int,text,练习,long,else,fa,20240924 From： https://www.cnblogs.com/y1wei/p/18429955