啦啦啦~
考试
粉刷匠
这个粉刷匠不是第一天 A 组的粉刷匠，不会用 $dp$ 的喔死磕半个多小时才把方程列出来，应该是：
$$ f[i][j][k]=max \{ f[i][j-1][k] + val, f[i][j-1][k-1] + val \} $$
我不知道是不是对的，最后收集答案时使用 $dfs$ 枚举，只加了一个最优化剪枝。
好的，是错的。QAQ
今天这道提高 B 组的 T1 在洛谷的难度是：
这让我的心态有了一点 小小 的变化 qwq
这题预处理一下就可以转换成一个背包问题，因为我不会，所以我也不知道 $dalao$ 们是怎么想出来的，只能原样照搬 qwq
首先设计状态：
- $f[i][k]$ ：表示前 $i$ 条木板一共粉刷 $k$ 次后的最大合法格子数
- $w[i][j][k]$ ：表示在第 $i$ 条木板上涂完前 $j$ 个格子后用了 $k$ 次粉刷的最大合法格子数
那么只需要预处理出 $w[i][j][k]$ ，就可以像背包问题一样转移 $f[i][j]$ 了。
对于 $f[i][j]$ 的转移，是显而易见的（在处理出 $w[i][j][k]$ 以后）：
$$ f[i][j] = max \{ f[i][j], f[i-1][j]+w[i][m][k] \} $$
其中：
- $m$ 是固定的，表示一行多少个
- $k$ 是不一定的，因为不知道刷多少次，所以要枚举一遍
对于 $w[i][j][k]$ 的预处理，在枚举 $i$ 、$j$ 、$k$ ，更新出最大值。对于计算更新后作出的贡献，可以加一个前缀和来方便计算。
设 $sum[i][j]$ 等于第 $i$ 行，前 $j$ 个蓝色格子（蓝色是 1 ，方便加）的个数。
那么对于一个区间中的红色格子：
$$ red[l,r]=sum[i][r]-sum[i][l] $$
对于一个区间的蓝色格子：
$$ blue[l,r]=(r-l)-(sum[i][r]-sum[i][l]) $$
那么对于 $w[i][j][k]$ 的处理：
$$ w[i][j][k]=max \{ w[i][j][k], w[i][l][k-1]+max \{ sum[i][j]-sum[i][l], (j-l)-(sum[i][j]-sum[i][l] \} \} $$
然后就完成了~~
$Test's$ $Code$：0%
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 50 + 5;
const int MAXM = 50 + 5;
const int MAXT = 25e2 + 5;
int n, m, T, ans;
int f[MAXN][MAXM][MAXT], col[MAXN][MAXM][MAXT];
int g[MAXN][MAXM], s[MAXN], Max[MAXN];
void dfs (int i, int k, int cnt) {
if (i > n) {
ans = max (ans, cnt);
return;
}
if (cnt + s[i] <= ans) {
return;
}
if (i == n) {
dfs (i + 1, 0, cnt + f[i][m][k]);
return;
}
for (int j = 0; j <= k; j++) {
dfs (i + 1, k - j, cnt + f[i][m][j]);
}
return;
}
int main() {
scanf ("%d%d%d", &n, &m, &T);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
g[i][j] = ch - '0';
}
}
for (int k = 1; k <= T; k++) {
for (int i = 1; i <= n; i++) {
if (k == 1) {
f[i][1][k] = 1;
col[i][1][k] = g[i][1];
}
for (int j = k + 1; j <= m; j++) {
int x = f[i][j - 1][k] + (g[i][j] == (col[i][j - 1][k]) ? 1 : 0);
int y = f[i][j - 1][k - 1] + (g[i][j] == (1 - col[i][j][k - 1]) ? 1 : 0);
if (x > y) {
f[i][j][k] = x;
col[i][j][k] = col [i][j - 1][k];
}
else {
f[i][j][k] = y;
col[i][j][k] = 1 - col[i][j - 1][k - 1];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout <<i<<" "<<j<<endl;
for (int k = 1; k <= T; k++) {
cout <<f[i][j][k]<<" ";
}
cout <<endl;
}
cout <<endl;
}
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= T; k++) {
Max[i] = max (Max[i], f[i][m][k]);
}
}
for (int i = n; i >= 1; i--) {
s[i] = s[i + 1] + Max[i];
}
dfs (1, T, 0);
printf ("%d\n", ans);
return 0;
}$Fixed$ $Code$：100%
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 50 + 5;
const int MAXM = 50 + 5;
const int MAXT = 25e2 + 5;
int n, m, t, a[MAXN][MAXM];
int f[MAXN][MAXT], w[MAXN][MAXM][MAXT], sum[MAXN][MAXM];
int main() {
scanf ("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >>ch;
a[i][j] = ch - '0';
sum[i][j] = sum [i][j - 1] + a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m; k++) {
for(int l = k - 1; l <= j - 1; l++) {
w[i][j][k] = max (w[i][j][k], w[i][l][k - 1] + max (sum[i][j] - sum[i][l], (j - l) - (sum[i][j] - sum[i][l])));
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= t; j++) {
for (int k = 0; k <= min (j, m); k++) {
f[i][j] = max (f[i][j], f[i - 1][j - k] + w[i][m][k]);
}
}
}
printf ("%d\n", f[n][t]);
return 0;
}迷路
什么倍增 + $Floyd$ + 矩阵快速幂？？？
等我学完矩阵快速幂再说 QAQ
游戏
这道题又是被几天前那个小学生巨佬讲解的 qwq，我要自闭了.....
题目要一个字符串还原，可以发现每一个数字都是会回到起点的，也就是一个循环，要想要他们都同时回到原处，就是求这些循环长度的最小公倍数。
网上很多都说了类似的一段话：
对于所有的环长 $L_i$ ，一定有 $\sum\limits_{i=1}^{n} L_i = n$。 ---网络
样例不就是 $3+3+3+2+2+1=14 \neq 6$ 吗？
好的，我太菜了，写完才反应过来，对于样例，有 （1，2，3）（4，5）（6） 这三组环。意思不是每个数的循环 qwq
emm，这样，问题就转化成：在 $n$ 的所有正整数拆分中，有多少个不相同的最小公倍数。
最小公倍数是可以转化为各个质因子的乘积的，这样，只要枚举质因子及其的幂，就一定可以枚举出不一样的最小公倍数。因为质因子可以取很多个，所以这就可以转换为完全背包问题。
先设一个二维的状态：$f[i][j]$ 表示前 $i$ 个质数的和为 $j$ 的情况数。
这样就可以很轻松的得出转移方程：
$$ f[i][j] = \sum\limits_{k=0}^{j-p_i^k \geq 0} f[i-1][j-p_i^k] $$
然后就可以倒一下循环的顺序就可以把二维降为一维，还有记得最后再循环一遍统计答案。
还有一点需要注意，对于 $n$ 的 “拆分”，其实 “拆分" 的各数之和小于 $n$ 也没有关系，因为可以用 1 补。
$Test's$ $Code$：30% （$\frac{12}{1000}$ 的打表还有 30 分，数据太感动（shui）了）
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e3 + 5;
int n, a[MAXN];
int main() {
scanf ("%d", &n);
a[1] = 1;
a[2] = 2;
a[3] = 3;
a[4] = 4;
a[5] = 6;
a[6] = 6;
a[7] = 9;
a[8] = 11;
a[9] = 14;
a[10] = 16;
a[11] = 20;
a[12] = 23;
printf ("%d\n", a[n]);
return 0;
}$Fixed$ $Code$：100%
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e3 + 5;
int n, p[MAXN], cnt;
long long f[MAXN], ans;
int main() {
scanf ("%d", &n);
p[++cnt] = 2;
for (int i = 3; i <= n; i += 2) {
int flag = true;
for (int j = 1; j <= cnt; j++) {
if (i % p[j] == 0) {
flag = false;
break;
}
}
if (flag) {
p[++cnt] = i;
}
}
f[0] = 1;
for (int i = 1; i <= cnt; i++) {
for (int j = n; j >= p[i]; j--) {
int temp = p[i];
while (temp <= j) {
f[j] += f[j - temp];
temp *= p[i];
}
}
}
for (int i = 0; i <= n; i++) {
ans += f[i];
}
printf ("%lld\n", ans);
return 0;
}windy数
听 $dalao$ 们说都是数位 $dp$ 的模板题，但是数位 $dp$ 喔不会啊 qwq
似乎差不多就是把每位分开来模拟 $dp$。
总结
失败的一天，没有订完题。QAQ
本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/77/
最后修改时间：2020-04-14 08:59:38
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！