20260914 每日 2.0 3.0 4.5

No.1160 奇怪保龄球

http://yukicoder.me/problems/no/1160

不难发现下一轮的状态只与上一轮有关，并且无后效，于是可以考虑 DP

状态分别是，这一轮触发加分，这一轮没触发加分，不难写出转移。

滚动数组还可以优化一下空间。

namespace XK {
  void solve() {
  	int N; in(N);
  	V<pair<int, int>> A(N); in(A);
  	int f[2]{0};
  	f[0] = A[0].fst, f[1] = A[0].snd;
  	Rep(i, 1, N) {
  		int nf[2]{0};
  		nf[0] = max(f[1] + 2 * A[i].fst, f[0] + A[i].fst);
  		nf[1] = max(f[1] + 2 * A[i].snd, f[0] + A[i].snd);
  		swap(f, nf);
  	}
  	out(max(f[0], f[1]));
  }
};

No.1474 かさまＪ

https://yukicoder.me/problems/no/1474

对于一个人有两种分法，假设分配的 p 数量是 $X_i$，q 数量是 $Y_i$：

• $Y_i = 0$：$X_i$ 无限制
• $Y_i \gt 0$：$X_i + Y_i \ge L$，这时等价于 $X_i - (L - Y_i) \ge 0$，也就是说，此时分配的 p 数量至少是 $L - Y_i$ 个。

那么我们有必须分配在指定位置的 p 数量就是 $\sum_{Y_i \gt 0} (L - Y_i)$，假设有 $k$ 个人有 q 且一共分配出去了 $Q$ 个 q 的话，那么至少分配的 p 数量就是 $k \times L - Q$ 个。

那么剩下的可以随意分配的 p 数量就是：$Rem = M_p - k \times L + Q$ 个，

这些东西分配到 $N$ 个人，这个等价于对 $Rem$ 隔板法，于是方案数就是：
$$
\binom{M_p - k \times L + Q + N - 1}{N - 1}
$$
这个时候只需要再求出来确定 $k$ 和 $Q$ 的情况下，q 的分配数就可以乘法原理得到答案了。

这个位置可以发现，处理前 $i$ 个人之后，未来的人只需要知道某些汇总信息，就能决定后续转移。这个汇总信息满足最优子结构/无后效性。这部分可以只通过一个二元组 $(k, Q)$ 表示当前的分配方案数，于是考虑动态规划：
$$
f(i)[k][Q] := 考虑到第 i 个人，前面有 k 个人分配了 q，分配总数是 Q 的方案数
$$
而第一维度显然可以用滚动数组优化掉，因为两个人之间不存在关系

于是考虑两种情况：

• 第 $i$ 个人不给 q：$f(i)[k][Q] += f(i-1)[k][Q]$ 即可
• 第 $i$ 个人给 q：那么就要考虑给的 q 数了，值域是 $t \in [1,S_i]$，$f_{i,k,Q} += \sum_{t=1}^{S_i} f_{i-1,k-1,Q-t}$ ，计数 DP 一般都是累加的，因为有多条边（选择方案）可以通过一步转移到最终方案

初始值显然是 $f(0)[0][0] = 1$。

但是这里有个问题，这个转移是 $O(N \times N \times M_q \times min(L, S))$ 的，但是通过前缀和就可以把那个部分的求和变成 $O(1)$ 的了，所以复杂度是 $O(N^2M_q)$ 的，可以通过。

最后只需要枚举 $k,Q$ ，然后加法原理乘法原理即可：
$$
Ans = \sum_{k=0}^N\sum_{Q=0}^{M_q} f_{k,Q} \times \binom{M_p + k \times L - Q + N - 1}{N - 1}
$$
当然我的代码实现常数很大，显然枚举 $j$ 内部的时候，里面枚举 $k$ 可以写得更聪明。

总复杂度是 $O(N^2M_q)$

namespace XK {
	// X_i + Y_i >= L => Z_i = X_i - (L - Y_i) >= 0 最低要求
	// Rem = Mp - kL + Q
	// {Mp - kL + Q + N - 1} C {N - 1}
const ll mod = 1e9 + 7;
struct mm {
};
struct Comb {
};
  void solve() {
  	Comb comb(1e6);
  	int N, Mp, Mq, L; in(N, Mp, Mq, L);
  	V<int> S(N); in(S);
  	V<V<mm>> f(N + 1, V<mm>(Mq + 1, 0));
  	f[0][0] = 1;
  	rep(i, N) {
  		V<V<mm>> nf(N + 1, V<mm>(Mq + 1, 0));
  		rep(j, i + 1) {
  			rep(k, Mq + 1)
  				nf[j][k] += f[j][k];
  			mm pre[Mq + 1]{0};
				rep(k, Mq + 1) {
					pre[k] = f[j][k];
					if(k) pre[k] += pre[k - 1];
				}
				rep(k, Mq + 1) {
					int r = k - 1;
					int l = max<int>(0, k - S[i]);
					if(r >= l) {
						nf[j + 1][k] += pre[r] - (l == 0 ? 0 : pre[l - 1]);
					}
				}
  		}
  		swap(f, nf);
  	}
  	mm ans = 0;
  	rep(k, N + 1) rep(q, Mq + 1) {
  		ans += f[k][q] * comb.C(Mp - k * L + q + N - 1, N - 1);
  	}
  	out(ans.x);
  }
};