AT_dp

本来是想提高一下DP，然后发现就只有几道蓝题有点启发性，紫题都是板题...

x

题目描述

你有 \(n\) 个箱子，编号从 \(1\) 到 \(n\)，每个箱子有三个属性，以第 \(i\) 个箱子为例，分别是重量 \(w_i\)，承重能力 \(s_i\)，价值 \(v_i\)。

你想建一座塔，因此需要将一些箱子堆叠起来，但是每个箱子必须满足下面的条件：

• 这个箱子上面的所有箱子重量和要小于等于这个箱子的承重能力。

定义一个塔的价值为它所用的所有箱子的价值和。

最大化这个塔的价值并输出它。

solution

可以考虑确定枚举顺序，然后dp，于是就考虑如何确定顺序

然后发现根据\(w_i+s_i\)排序，然后跑背包即可

y

题目描述

给一个 \(H\times W\) 的网格，每一步只能向右或向下走，给出一些坐标，这些坐标对应的位置不能经过，求从左上角 \((1,1)\) 走到右下角 \((H,W)\) 的方案数，答案对 \(10^9+7\) 取模。

solution

考虑设\(f_{x}\)表示走到第x个障碍所在位置，且在此之前没有走过障碍的方案数，那么加入一个\((H,W)\)障碍即可得到答案

考虑如何转移，考虑用合法方案减去非法方案，朴素的子集容斥肯定会T，于是考虑代表元容斥，那么不合法方案数即为\(\sum_{y<x} c(x,y)f_y\)，\(c(x,y)\)表示x到y的方案数

t

题目描述

有一个长为 \(N\) 的正整数排列。给定一个由 < 和 > 组成长为 \(N-1\) 的字符串。
对于任意满足 \(1 \le i \le N-1\) 的字符 \(s_i\)，如果 \(s_i\) 是 < 则 \(P_i<P_{i+1}\)、如果 \(s_i\) 是 > 则 \(P_i>P_{i+1}\)。求满足这样的性质的排列 \(P\) 的方案数。

solution

穿岩十九峰的弱化，考虑一个相对顺序，设\(f_{i,j}\)表示到第i个数，它在前i个中排名第j，然后用前缀和优化转移即可

撅密

联考有一道题...

给定一个由 < 和 > 组成长为 \(N-1\) 的字符串和A,B。

满足 \(s_i\) 是 < 且\(P_i<P_{i+1}\)或者 \(s_i\) 是 > 且 \(P_i>P_{i+1}\)的位置个数为x，满足\(P_i=i\)的个数为y，那么定义一个排列的贡献为\(A^x\times B^y\)。求所有排列的贡献和

题目的难点在于同时求两个问题，所以我的思路是先分别写两个dp

第一个和dp_t一样，另外就是错排问题，我们发现两个dp第一维的含义不同

w

题目描述

给定 \(m\) 条规则形如 \((l_i,r_i,a_i)\)，对于一个 01 串，其分数的定义是：对于第 \(i\) 条规则，若该串在 \([l_i,r_i]\) 中至少有一个 1，则该串的分数增加 \(a_i\)。

你需要求出长度为 \(n\) 的 01 串中的最大分数。

\(1\le n,m\le 2\times 10^5\)，\(|a_i|\le 10^9\)。

solution

NOIP2023T4的弱化...

首先设\(f_i\)表示到第i个位置且填了1的最大分数（只统计\(l\le i\)），然后就直接转移，对于一个\(r_x=i\)，就更新\((l_x,r_x)\)，然后可以用线段树优化

v

换根

z

斜率优化