题解：AT_arc204_a [ARC204A] Use Udon Coupon

观察基本条件。相当于是各实施

n

次操作 1 和操作 2。然后在任意时刻你已经实施的操作 2 次数不能大于操作 1 的次数。

参照 Iniaugoty 大佬的思路（最好先看一下他的题解，看懂就不用看我的了），把操作 1 想象成一条斜上的直线，操作 2 想象成斜下的直线。

由于每次我们 x 轴方向和 y 轴方向移动的距离相等，所以斜率也是相等的，只有斜上和斜下之分。把图画出来大概长这样。

注释：我这里要说一下，我画完图之后才发现自己画的不严谨，第一次操作只能是操作 1，因此图像的第一个折线应该只能是斜下的。不过懒得重画了，领会精神即可。

图像画出来大概长成这个样子（蓝）。

题目中的条件 “将

C

替换为

\max(0, C - A_{i})

“，其实就相当于图像碰到 x 轴之后不继续往下，而是水平向右延申。

那么图像其实就长成这个样子（红）。

你发现，最右边那一段，红色的图像是比蓝色要长的。这长的一段距离，也就是蓝色图像在 x 轴以下的距离。

因为我们只考虑结束点的 y 值，也就是

C

的最终值，所以我们可以直接把蓝色图像向上平移。得到绿色图像。

绿色图像的结束点和红色图像的结束点的 y 值一样。

我们考虑到平移的距离其实就是蓝色最低点离 x 轴的距离，那么我们设它为

low

。

由此表示绿色图像的最终点纵坐标，也就是红色图像的最终点纵坐标，也就是

C

。

C = \sum_{i = 1}^{n} b_i - \sum_{i = 1}^{n} a_i + low

= sumb_n - suma_n + low

然后把

C

代入题目中的不等式，解得

suma_n - sumb_n - R \leq low \leq suma_n - sumb_n - L

这个不等式容斥做一下就行。

然后我们就 dp 呗，计算已经实施了前

i

个操作 1，前

j

个操作 2 ，并且满足限制条件的方案数。

小细节是，发现不满足限制条件要直接 continue 掉，也不能给后面转移。因为我们设

low

是全局的最小值，如果有小于它的值一定不合法。

CPP

#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 5005, mod = 998244353;
int ans, n, l, r, L, R, suma[N], sumb[N], f[N][N], g[N][N];
inline void gm(int &x) {
	if(x >= mod) {
		x -= mod;
	}
}
signed main() {
	cin >> n >> L >> R;
	rep(i, 1, n) {
		cin >> suma[i];
		suma[i] += suma[i - 1];
	}
	rep(i, 1, n) {
		cin >> sumb[i];
		sumb[i] += sumb[i - 1];
	}
	l = sumb[n] - suma[n] - R, r = sumb[n] - suma[n] - L + 1;
	f[0][0] = g[0][0] = 1;
	rep(i, 1, n) {
		rep(j, 0, i) {
			if(sumb[j] - suma[i] < l) continue;
			if(j) {
				f[i][j] = f[i][j] + f[i][j - 1];
				gm(f[i][j]);
			}
			f[i][j] = f[i][j] + f[i - 1][j];
			gm(f[i][j]);
			
		}
	}
	rep(i, 1, n) {
		rep(j, 0, i) {
			if(sumb[j] - suma[i] < r) continue;
			if(j) {
				g[i][j] = g[i][j] + g[i][j - 1];
				gm(g[i][j]);
			}
			g[i][j] = g[i][j] + g[i - 1][j];
			gm(g[i][j]);
		}
	}
	cout << (f[n][n] - g[n][n] + mod) % mod;
	return 0;
}

题解：AT_arc204_a [ARC204A] Use Udon Coupon

文章操作

相关推荐

评论

题解：AT_arc204_a [ARC204A] Use Udon Coupon