标签：ons   方案   back   思路   节点   mod   bool   open   背包   

[JSOI2018]潜入行动 解题报告

链接

题面

题目大意

一棵节点为 \(n\) 的树, 有 \(k\) 个装置. 当点 \(u\) 上安装了装置后, 对于所有 \((u,v)\), 点 \(v\) 都会被覆盖.

要求每个点上最多只能安装一个装置, \(k\) 个装置必须被用完.

求树上所有节点都被覆盖的方案数.

数据范围

\(1\le n \le 10^5,1 \le k \le \min(n,100)\).

思路

容易想到一个 \(DP\), 设 \(f[u][j][0/1/2/3]\) 分别表示点 \(u\) 处于 \(0/1/2/3\) 状态时, 子树中安装了 \(j\) 个装置的方案数. \(0/1/2/3\) 分别的意义如下.

• \(0\) : 点 \(u\) 上没有安装装置, 也没有被覆盖.
• \(1\) : 点 \(u\) 上没有安装装置, 但被覆盖了.
• \(2\) : 点 \(u\) 上安装了装置, 但没有被覆盖.
• \(3\) : 点 \(u\) 上安装了装置, 并且被覆盖了.

转移的时候要保证 \(u\) 的子树中除了 \(u\) 以外的点都被覆盖了.

并且转移的时候先用一个 \(tmp\) 数组来记录新的 \(f\) 值, 避免转移顺序发生混乱. (树形背包的常用做法)

这个 \(DP\) 看上去是 \(O(nk^2)\) 的, 实际上可以证明是 \(O(nk)\) 的.

假设我们现在需要合并的两个背包为 \(f[u]\) 和 \(f[v]\), 我们分三种情况讨论.

1. $sz[u] \ge k \ \rm and\ $$sz[v] \ge k$ : 这时合并的复杂度是 \(O(k^2)\), 但这种情况只会出现 \(O\left(\frac{n}{k}\right)\) 次, 所以总复杂度还是 \(O(nk)\).
2. $sz[u] \ge k \ \rm and\ $$sz[v] \(v\)

在上述三种情况下, 时间复杂度都是 \(O(nk)\), 所以总时间复杂度也是 \(O(nk)\).

但由于常数比较大 (转移方程比较复杂), 并且空间给的比较小 (\(250\)MB, 不能开 \(long long\)), 所以需要卡卡常.

代码

#include

using namespace  std;

#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;

const int _=1e2+7;
const int __=1e5+7;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

bool be;
int n,K;
int f[__][_][4],tmp[_][4];
vector to[__];
bool en;

void Init(){
    cin>>n>>K;
    int x,y;
    for(int i=1;i>x>>y;
	to[x].pb(y),to[y].pb(x);
    }
}

void Upd(int &x,ll y){ x= (ll)x+y>=mod ?(ll)(x+y)%mod :x+y; }

int Min(int a,int b){ return a

[JSOI2018]潜入行动 解题报告

标签：ons   方案   back   思路   节点   mod   bool   open   背包   

原文地址：https://www.cnblogs.com/BruceW/p/13131819.html