20240709基础动态规划专题
20240709基础动态规划专题
BZOJ1742 抢鲜草
设 \(f_{l,r,0/1}\) 表示已经吃完了区间 \(l\) ~ \(r\)，现在在 \(l\) 还是 \(r\) 时的最小损失值。
转移：
\[f_{l,r,0} = \min (f_{l+1,r,0} + (l + n - r) \times |a_l - a_{l+1}|, f_{l+1,r,1} + (l + n - r) \times |a[l] - a[r]|)
\]
\[f_{l,r,1} = \min(f_{l,r-1,1} + (l + n - r) \times |a_r - a_{r-1}|, f_{l,r-1,0} + (l + n - r) \times |a[r] - a[l]|);
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
//# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 1005;
int n, k;
int a[N];
int dp[N][N][2]; // l-r is eaten, now is at l/r
signed main ()
{
read (n, k);
for (int i = 1; i <= n; i ++ ) read (a[i]);
sort (a + 1, a + 1 + n);
for (int len = 1; len <= n; len ++ )
{
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
if (l == r) dp[l][r][0] = dp[l][r][1] = abs (a[l] - k) * n;
else
{
dp[l][r][0] = min (dp[l + 1][r][0] + (l + n - r) * abs (a[l] - a[l + 1]), dp[l + 1][r][1] + (l + n - r) * abs (a[l] - a[r]));
dp[l][r][1] = min (dp[l][r - 1][1] + (l + n - r) * abs (a[r] - a[r - 1]), dp[l][r - 1][0] + (l + n - r) * abs (a[r] - a[l]));
}
}
}
write (min (dp[1][n][0], dp[1][n][1]), '\n');
return 0;
}
P4161 [SCOI2009] 游戏
对每个数按关系建边，很容易发现会形成若干个环。那么，题目中要求的其实就是环大小的最小公倍数的个数。
模拟样例，可以发现：每个环所包含的数字都是固定的。那么问题可以转化为：将 \(n\) 个数分成 \(m\) 个集合，求这些集合中元素个数的最小公倍数的个数
最小公倍数可以变为若干每个质因子 \(p_i\) 的乘积，所以就可以根据这个设计状态：\(f_{i,j}\) 表示前 \(i\) 个质数，总和为 \(j\) 的方案数。
转移：
\[f_{i,j} = \sum_{k\ge 0,j-p_i^k\ge 0}{f_{i-1,j-p_i^k}}
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
# define int ll
# define lc u << 1
# define rc u << 1 | 1
const int N = 10005;
int n, mod;
bool com[N];
int pri[N], tot;
void sieve ()
{
com[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!com[i]) pri[ ++ tot] = i;
for (int j = 1; j <= tot && i * pri[j] < N; j ++ )
{
com[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
int f[N]; // pri 1~i, sum is j, the max val
signed main ()
{
read (n);
sieve ();
f[0] = 1;
for (int i = 1; i <= tot; i ++ )
{
for (int j = n; j >= pri[i]; j -- )
{
int w = pri[i];
while (w <= j)
{
f[j] = (f[j] + f[j - w]);
w *= pri[i];
}
}
}
int ans = 0; for (int i = 0; i <= n; i ++ ) ans = (ans + f[i]);
write (ans, '\n');
return 0;
}
P6280 [USACO20OPEN] Exercise G
还是上一题的状态，转移改一改：
\[f_{i,j} = \sum_{k\ge 0,j-p_i^k\ge 0}{f_{i-1,j-p_i^k}} \times p_i^k
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
# define int ll
# define lc u << 1
# define rc u << 1 | 1
const int N = 10005;
int n, mod;
bool com[N];
int pri[N], tot;
void sieve ()
{
com[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!com[i]) pri[ ++ tot] = i;
for (int j = 1; j <= tot && i * pri[j] < N; j ++ )
{
com[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
int f[N]; // pri 1~i, sum is j, the max val
signed main ()
{
read (n, mod);
sieve ();
f[0] = 1;
for (int i = 1; i <= tot; i ++ )
{
for (int j = n; j >= pri[i]; j -- )
{
int w = pri[i];
while (w <= j)
{
f[j] = (f[j] + f[j - w] * w % mod) % mod;
w *= pri[i];
}
}
}
int ans = 0; for (int i = 0; i <= n; i ++ ) ans = (ans + f[i]) % mod;
write (ans, '\n');
return 0;
}
P6570 [NOI Online #3 提高组] 优秀子序列
妙啊
因为有与操作，所以可以把每个数字看成一个二进制集合。然后题目中的 \(a\& b=0\) 也就是 \(a\) 和 \(b\) 的空集。
设 \(f_i\) 表示选出的数和为 \(i\) 的方案数。那么最终答案就是
\[\sum_{x}{f_x \varphi(x+1)}
\]
转移：
\[f_s = \sum_{x\subseteq s,y=\complement_{s}{x}}{f_y(x 在序列中出现的次数)}
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
//# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 1000005, mod = 1e9 + 7;
int n;
int cnt[N];
ll dp[N], m, ma; // m是最大值的位数
int pri[N], phi[N], tot;
void sieve ()
{
phi[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!phi[i]) pri[ ++ tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * pri[j] < N; j ++ )
{
if (i % pri[j] != 0) phi[i * pri[j]] = (pri[j] - 1) * phi[i];
else
{
phi[i * pri[j]] = pri[j] * phi[i];
break;
}
}
}
}
int f[N];
signed main ()
{
sieve ();
read (n);
int mx = 0;
for (int i = 1; i <= n; i ++ )
{
int x; read (x);
cnt[x] ++ ;
mx = max (mx, x);
}
int m = 0;
while (mx >= (1 << m)) m ++ ;
mx = (1 << m);
dp[0] = 1;
for (int s = 1; s <= mx; s ++ )
{
for (int t = s; ; t = (t - 1) & s)
{
int Ct = s ^ t;
if (t < Ct) break;
dp[s] = (dp[s] + dp[Ct] * cnt[t]) % mod;
}
}
int ans = 1; // empty
for (int i = 1; i <= mx; i ++ ) ans = (ans + dp[i] * phi[i + 1]) % mod;
for (int i = 1; i <= cnt[0]; i ++ ) ans = (ans * 2) % mod;
write (ans, '\n');
return 0;
}
CF1280D Miss Punyverse
好难啊
首先，设每个点的权值 \(a_i\) 为 \(w_i-b_i\)。
容易设出 \(f_{u,i}\) 表示以 \(u\) 这个点为根的子树分成了 \(i\) 块，不算 \(u\) 在的那一块的最大连通块个数。但是因为不知道 \(u\) 那一块的权值，感觉很难转移。
假设如果有两种方案所分出的块数相等，那么肯定是权值越大越好。所以可以设 \(g_{u,i}\) 表示在块数为 \(f_{u,i}\) 时，\(u\) 那一块的最大权值。
转移：
- 如果 \(v\) 与 \(u\) 不在同一个块里
\[f_{u,i+j}=f_{u,i}+f_{v,i}+(g_{v,j}>0)\\
g_{u,i+j}=g_{u,i}
\]
- 如果 \(v\) 与 \(u\) 在同一个块里
\[f_{u,i+j-1}=f_{u,i}+f_{v,j}\\
g_{u,i+j-1}=g_{u,i}+g_{v,j}
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 3005;
int n, m;
int b[N], w[N], a[N];
vector <int> e[N];
int sz[N];
int f[N][N], g[N][N];
// f[u][i]: rt is u, seperate the subtree into i parts, the mx num of pars
// g[u][i]: when the parts num is f[u][i], the mx val of the part that u is in
int tmpf[N], tmpg[N];
void dfs (int u, int fa)
{
sz[u] = 1;
f[u][1] = 0, g[u][1] = a[u];
for (int v : e[u])
{
if (v == fa) continue;
dfs (v, u);
memset (tmpf, 0, sizeof tmpf), memset (tmpg, -0x3f3f3f3f, sizeof tmpg);
for (int i = 1; i <= min (sz[u], m); i ++ )
{
for (int j = 1; j <= min (sz[v], m); j ++ )
{
int nf = f[u][i] + f[v][j] + (g[v][j] > 0), ng = g[u][i];
// v connet with u
if (i + j <= m &&
(nf > tmpf[i + j] || nf == tmpf [i + j] && ng > tmpg[i + j]))
tmpf[i + j] = nf, tmpg[i + j] = ng;
nf -= (g[v][j] > 0), ng += g[v][j];
if (i + j - 1 <= m &&
(nf > tmpf[i + j - 1] || nf == tmpf[i + j - 1] && ng > tmpg[i + j - 1]))
tmpf[i + j - 1] = nf, tmpg[i + j - 1] = ng;
}
}
for (int i = 1; i <= min (sz[u] + sz[v], m); i ++ )
f[u][i] = tmpf[i], g[u][i] = tmpg[i];
sz[u] += sz[v];
}
}
signed main ()
{
int T; read (T);
while (T -- )
{
read (n, m);
for (int i = 1; i <= n; i ++ ) e[i].clear ();
for (int i = 1; i <= n; i ++ ) read (b[i]);
for (int i = 1; i <= n; i ++ ) read (w[i]);
for (int i = 1; i <= n; i ++ ) a[i] = w[i] - b[i];
for (int i = 1; i < n; i ++ )
{
int u, v; read (u, v);
e[u].push_back (v), e[v].push_back (u);
}
memset (f, 0, sizeof f), memset (g, -0x3f3f3f3f, sizeof g);
dfs (1, 0);
write (f[1][m] + (g[1][m] > 0), '\n');
}
return 0;
}
CF1500D Tiles for Bathroom
不妨固定一个右下角 \((i,j)\)，计算即使 \(k\) 的取值。对于一个点\((x,y)\)，\(\operatorname{max}(i-x,i-y)+1\le k\)。切比雪夫距离为 \(\operatorname{max}(i-x,i-y)\)。
所以题面可以转化为求距离 \((i,j)\) 前 \(q+1\) 个颜色（因为 \(q+1\) 个颜色，刚好超）。考虑到距离 \((i,j)\) 前 \(q+1\) 个颜色的位置的点一定由距离 \((i-1,j),(i,j-1),(i-1,j-1)\) 前 \(q+1\) 个颜色的位置转移过来。
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 1505, M = N * N;
int n, k;
int a[N][N];
int getdis (int xa, int ya, int xb, int yb) { return max (abs (xb - xa), abs (yb - ya)); }
vector < pair <int, int> > vec[2][N];
bool vis[M];
int _x, _y;
ll ans[N];
signed main ()
{
read (n, k);
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
read (a[i][j]);
}
int op = 0;
for (int i = 1; i <= n; i ++ )
{
op ^= 1;
for (int j = 1; j <= n; j ++ )
{
vec[op][j].clear ();
vec[op][j].push_back ({i, j});
if (i)
{
for (auto x :vec[op ^ 1][j])
vec[op][j].push_back (x);
}
if (j)
{
for (auto x : vec[op][j - 1])
vec[op][j].push_back (x);
}
if (i && j)
{
for (auto x : vec[op ^ 1][j - 1])
vec[op][j].push_back (x);
}
_x = i, _y = j;
sort (vec[i & 1][j].begin (), vec[i & 1][j].end (),
[](const pair <int, int> &a, const pair <int, int> &b)
{
int xa = a.first, ya = a.second, xb = b.first, yb = b.second;
return getdis (xa, ya, _x, _y) < getdis (xb, yb, _x, _y);
});
vector < pair <int, int> > ve;
int res = 1e9;
for (auto t : vec[i & 1][j])
{
int x = t.first, y = t.second;
if (!vis[a[x][y]])
{
vis[a[x][y]] = 1;
ve.push_back (t);
if ((int)ve.size () == k + 1)
{
res = getdis (x, y, _x, _y);
break;
}
}
}
vec[i & 1][j] = ve;
for (auto x : ve) vis[a[x.first][x.second]] = 0;
ans[min ({i, j, res})] ++ ;
}
}
for (int i = n - 1; i >= 1; i -- ) ans[i] += ans[i + 1];
for (int i = 1; i <= n; i ++ ) write (ans[i], '\n');
return 0;
}
CF1276D Tree Elimination
设 \(f_{u,0/1/2/3}\) 表示：\(u\) 是被自己父亲之前的边覆盖的，\(u\) 是被自己父亲覆盖的，\(u\) 是被自己父亲后边的边覆盖的，\(u\) 没有被覆盖。
转移：
\[f_{u,0}=\sum_{v\in son_u}{(f_{v,2/3}\times \coprod_{(u,w)在(u,v)之前}{f_{w,0/1}\times \coprod_{(u,w)在(u,w)之后}{f_{w,0,2,3}}})}\\
f_{u,1}=\coprod_{v\in son_u,(u,v)在(u,fa_u)之前}{f_{v,0/1}\times \coprod_{v\in son_u,(u,v)在(u,fa_u)之后}{f_{v,0/2/3}}}\\
f_{u,3}=\coprod_{v\in son_u}{f_{v,0/1}}
\]
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 200005, mod = 998244353;
int n;
vector <int> e[N];
int f[N][4];
// f[u][0]: u is covered before its father
// f[u][1]: u is covered by its father
// f[u][2]: u is covered after its father
// f[u][3]: u is not covered
int mul01[N], sum23[N], sum023[N], tot;
void dfs (int u, int fa)
{
for (int v : e[u])
{
if (v == fa) continue;
dfs (v, u);
}
int faid = 0; tot = 0;
mul01[0] = 1;
for (int v : e[u])
{
if (v == fa) { faid = tot; continue; }
tot ++ ;
mul01[tot] = mul01[tot - 1] * (f[v][0] + f[v][1]) % mod;
sum23[tot] = (f[v][2] + f[v][3]) % mod;
sum023[tot] = (sum23[tot] + f[v][0]) % mod;
}
for (int i = tot - 1; i >= 0; i -- ) sum023[i] = (sum023[i] * sum023[i + 1]) % mod;
sum023[tot + 1] = 1;
for (int i = 1; i <= tot; i ++ )
{
if (i <= faid) f[u][0] = (f[u][0] + mul01[i - 1] * sum23[i] % mod * sum023[i + 1] % mod) % mod;
else f[u][2] = (f[u][2] + mul01[i - 1] * sum23[i] % mod * sum023[i + 1] % mod) % mod;
}
f[u][1] = mul01[faid] * sum023[faid + 1] % mod;
f[u][3] = mul01[tot];
}
signed main ()
{
read (n);
for (int i = 1; i < n; i ++ )
{
int u, v; read (u, v);
e[u].push_back (v), e[v].push_back (u);
}
dfs (1, 0);
write ((f[1][0] + f[1][2] + f[1][3]) % mod, '\n');
return 0;
}
[省选联考 2021 A/B 卷] 滚榜、
数据范围告诉我们，应该考虑状压。
设 \(f_{S,i,j,k}\) 表示已经滚完的人的状态是 \(S\)，滚完了 \(i\) 个人，现在滚榜期间过题数量为 \(j\)，上一个 \(b_i\) 为 \(k\) 的方案数。但是十分慢，考虑优化。
显然，我们可以记录一个 \(j\) 要超过 \(i\) 的代价 \(d_{i,j}\)。然后，费用提前计算。
# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
using namespace std;
typedef long long ll;
# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 20, M = (1 << 13) + 5;
int n, m, full;
int a[N];
int d[N][N]; // the val j need to add to win i
int mxval[N]; // the val i need to add to be the max
int f[M][N][505];
// fsij: people in s is rolled, the last people is i, the sum of bi is j
int pcnt[1 << N]; long long ans;
signed main ()
{
read (n, m);
for (int i = 1; i <= n; i ++ ) read (a[i]);
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
if (j <= i) d[i][j] = max (0ll, a[i] - a[j]);
else d[i][j] = max (0ll, a[i] - a[j] + 1);
}
}
for (int j = 1; j <= n; j ++ )
{
for (int i = 1; i <= n; i ++ )
mxval[j] = max (mxval[j], d[i][j]);
}
for (int i = 1; i <= n; i ++ )
{
if (n * mxval[i] <= m)
f[1 << (i - 1)][i][n * mxval[i]] = 1;
}
for (int s = 0; s < (1 << n); s ++ )
{
for (int i = 1; i <= n; i ++ )
{
if (s >> (i - 1) & 1)
{
int t = s ^ (1 << (i - 1));
int val = n - __builtin_popcount (t);
for (int j = 1; j <= n; j ++ )
{
if (i != j && (s >> (j - 1) & 1))
{
for (int k = d[j][i] * val; k <= m; k ++ )
f[s][i][k] += f[t][j][k - d[j][i] * val];
}
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
ans += f[(1 << n) - 1][i][j];
}
write (ans, '\n');
return 0;
}