|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 柿子饼同学 于 2024-7-28 20:57 编辑
总结与反思  
E (二进制枚举 排序优化)
dp转移需要求上一个权值比自己小的和直接通过排序, 离散化, 前缀和优化
F (区间dp)
很多时候状态是冗余的, 尽量缩小状态的范围, 不会就打印下来看看或者贪心证明
G (树形dp)
问你和深度有关, 一般想到枚举一条链(一端确定), 转移时一定要紧靠dp状态的含义
H (状压dp)
状态奇怪也不用怕, 大胆写, 先把已经有的变量放在一起看看能出什么, 遇到值很小的考虑状压, 一定看题才知道初始/最终状态的设置
E - 数位清除
有一个序列 a, a + 1, a + 2, ... a + N (a < 1e9, n < 100)
现可以进行任意次操作，每次操作可以把某个数上的某一位数字删除，形成一个新的数字。
每个数可以操作任意次，但不可以把一个数全部删完。
求有多少种方案，使得最后的序列中的数是单调不递减的。
注：两种方案是认为不同，当且仅当存在，第个数的第位在一个方案中被删除，在另一个方案中，没有被删除。
枚举出每个数字删除后的所有可能数字, 朴素的方法是 f(i, j) += f(i-1, k) 当 k 代表的数小于 j 代表的数
但是这样效率不高, 可以优化, 把数字排序之后转移就可以更快, 再加上前缀和优化#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
const int N = 13;
const int M = 105;
ll f[M][(1 << N)];
ll ava[M][(1 << N)]; // 把每个数的所有可能性数字放进去, 转移时二分答案即可
ll a, n;
int digit[M][N], top[M];
ll getnum(int id, int st) {
ll res = 0;
for (int i = top[id] - 1; ~i; i--) {
if ((st >> i) & 1)
res = res * 10 + digit[id][i];
}
return res;
}
void Init() {
for (int i = 0; i <= n; i++) {
ll temp = a + i;
while (temp) {
digit[i][top[i]++] = temp % 10;
temp /= 10;
}
// 所有数字可能性全部放进去
for (int j = 1; j < (1 << top[i]); j++) {
ava[i][++ava[i][0]] = getnum(i, j);
}
sort(ava[i] + 1, ava[i] + ava[i][0] + 1);
}
for (int i = 1; i <= ava[0][0]; i++) f[0][i] = f[0][i - 1] + 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a >> n;
Init();
for (int i = 1; i <= n; i++) {
// 必须设成 0, 不然一开始就假定比 i - 1 大了, 可能不合法
int k = 0;
for (int j = 1; j <= ava[i][0]; j++) {
// 这里用 lower_bound 会少情况, 因为它找的是第一个大于等于的
// int k = upper_bound(ava[i - 1] + 1, ava[i - 1] + ava[i - 1][0] + 1, ava[i][j]) - ava[i - 1] -
// 1;
while (k < ava[i - 1][0] && ava[i - 1][k + 1] <= ava[i][j]) k++;
f[i][j] = (f[i][j] + f[i - 1][k]) % P;
f[i][j] = (f[i][j] + f[i][j - 1]) % P;
}
}
cout << f[n][ava[n][0]];
return 0;
}
给定 n ( < 700) 个节点对应的权值 ，要求构造二叉搜索树（二叉树，左儿子节点权值小于父亲节点，右儿子节点权值大于父亲节点），且相邻节点的权值不互质。
问是否能成功构造满足要求的二叉搜索树。
枚举根, 分出两个子区间, 递归判定即可#include <bits/stdc++.h>
using namespace std;
const int N = 705;
// f[l][r][rt] = 0/1 可行性, 但是 rt 只可能在 l-1 或 r+1 上, 直接压掉
bitset<N> f[2][N], vis[2][N];
int n, a[N];
bool check(int a, int b) { return (__gcd(a, b) > 1); }
bool dp(int l, int r, int rt) {
if (l > r)
return 1;
// 记忆化
if (vis[rt][l][r])
return f[rt][l][r];
vis[rt][l][r] = 1;
// 父节点的位置 pa
int pa = l - 1;
if (rt == 1)
pa = r + 1;
if (l == r) {
if (check(a[l], a[pa]))
f[rt][l][r] = 1;
return f[rt][l][r];
}
bool cur = 0;
for (int i = l; i <= r; i++) {
// i 可以做 f 子树的根节点
if (check(a[i], a[pa])) {
cur = cur || (dp(l, i - 1, 1) && dp(i + 1, r, 0));
}
}
f[rt][l][r] = cur;
return cur;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (dp(1, n, 0))
cout << "Yes";
else
cout << "No";
return 0;
}
一棵有根树有 n (<4000) 个节点，每个节点的权值为 c，这棵树高度为 h。
可以执行任意多次以下操作：
选择一个点和以它为根的子树，将其剪去。
最后留下的树要满足以下条件
1、树节点数 - 树的高度 <= k ( < 500)。
2、余下的点权值之和最大。
求这个权值和。
注：
一， 1节点为树根，不能把它剪掉。
二， 1个节点的树高度为1。
看到高度想到枚举一个链, 别的发散出去的点数另算, 最后计算出的状态范围是 k
一个小性质: 一条链长度增加答案一定更优, 因为深度也增加了, 所以答案在叶子上
因为dp的转移有顺序, 我们对于一条链不能直接求出它伸展出去点个数权值的最大值, 所以可以拼
状态大胆设#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
const int M = 505;
// lft[u][x] 链[1, u] 左边伸展出 x 个点的最大值
int lft[N][M], rgt[N][M], sum[N];
int c[N], n, k, ans;
vector<int> e[N];
void Left(int u) {
for (auto ed : e[u]) {
sum[ed] = sum[u] + c[ed];
for (int i = 0; i <= k; i++) {
lft[ed][i] = lft[u][i];
}
Left(ed);
for (int i = 1; i <= k; i++) {
lft[u][i] = max(lft[u][i], lft[ed][i - 1] + c[ed]);
}
}
}
void Right(int u) {
for (int i = e[u].size() - 1; ~i; i--) {
int ed = e[u][i];
for (int j = 0; j <= k; j++) {
rgt[ed][j] = rgt[u][j];
}
Right(ed);
for (int j = 1; j <= k; j++) {
rgt[u][j] = max(rgt[u][j], rgt[ed][j - 1] + c[ed]);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int pa;
cin >> pa >> c[i];
e[pa].emplace_back(i);
}
sum[1] = c[1];
Left(1);
Right(1);
for (int i = 1; i <= n; i++) {
if (!e[i].empty())
continue;
// 拼起来
for (int j = 0; j <= k; j++) {
ans = max(ans, sum[i] + lft[i][j] + rgt[i][k - j]);
}
}
cout << ans;
return 0;
}
有n个数，可以移动这些数，但要满足在原来第i个数前面的数的编号必须小于等于i+B_i，求最小的相邻异或和。
这里设计状态的时候首先肯定想到记录上一个数, 前 i 个数已经算完
然后看到 B 小于 8 , 感觉状压一下 i 后面 7 个点的吃饭情况
一定要注意 1 号商品是 0 时间的
遇到古怪的状态大胆设#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n, cas;
ll t[N], b[N];
ll f[N][16][260];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> cas;
while (cas--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i] >> b[i];
}
memset(f, 0x3f, sizeof(f));
// 0 = +8 - 8
// 初始: 上一个人是 -1, 用的时间是 0
f[1][-1 + 8][0] = 0;
for (int i = 1; i <= n; i++) {
for (int st = 0; st < (1 << 8); st++) {
for (int last = -8; last < 8; last++) {
if (st & 1) {
f[i + 1][last + 8 - 1][st >> 1] =
min(f[i + 1][last + 8 - 1][st >> 1], f[i][last + 8][st]);
} else {
ll s = 1e18;
for (int k = 0; k <= b[i]; k++) {
// 选择一个 i 后面的没有选过的
if (!((st >> k) & 1)) {
if (i + k > s)
break;
s = min(s, i + k + b[i + k]);
// (i + last ? t[i + last] ^ t[i + k] : 0)
// 这句话的意思是判断上一个人是不是 0 , 如果是那这段时间就不用计算
f[i][k + 8][st | (1 << k)] =
min(f[i][k + 8][st | (1 << k)],
f[i][last + 8][st] + (i + last ? t[i + last] ^ t[i + k] : 0));
}
}
}
}
}
}
ll ans = 1e18;
for (int i = 0; i <= 8; i++) ans = min(ans, f[n + 1][i][0]);
cout << ans << '\n';
}
return 0;
}
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-7-7 22:07:03
置顶卡
千斤顶
显身卡
发表于 2024-7-7 22:57:36