靠前冲刺Day5

qbxt靠前冲刺Day5

T1

题面

现在有四种颜色的东西，各有$n_1,n_2,n_3,n_4$个。你需要把他们放到一排里面，并且保证相邻的东西颜色不同，问方案数。

Subtask 1 $n_1+n_2+n_3+n_4\leq10$

爆搜

Subtask 2 $n_1=0,n_2,n_3,n_4\leq50$

令$dp_{i,j,l,k}$表示第二、三、四种球已经填了$i,j,l$种，并且以第$k$种球结尾的方案数

那么可以推出，$dp_{1,0,0,1}=dp_{0,1,0,2}=dp_{0,0,1,3}=0$

转移看代码得了

namespace solve2 {
	long long dp[60][60][60][5];
	inline void solve() {
		dp[1][0][0][1] = dp[0][1][0][2] = dp[0][0][1][3] = 1;
		for (register int i = 0; i <= n[2]; ++i)
			for (register int j = 0; j <= n[3]; ++j)
				for (register int l = 0; l <= n[4]; ++l)
					for (register int k = 1; k <= 3; ++k) {
						if (k == 1)
							dp[i][j + 1][l][2] = (dp[i][j + 1][l][2] + dp[i][j][l][k]) % mod,
							dp[i][j][l + 1][3] = (dp[i][j][l + 1][3] + dp[i][j][l][k]) % mod;
						else if (k == 2)
							dp[i + 1][j][l][1] = (dp[i + 1][j][l][1] + dp[i][j][l][k]) % mod,
							dp[i][j][l + 1][3] = (dp[i][j][l + 1][3] + dp[i][j][l][k]) % mod;
						else
							dp[i][j + 1][l][2] = (dp[i][j + 1][l][2] + dp[i][j][l][k]) % mod,
							dp[i + 1][j][l][1] = (dp[i + 1][j][l][1] + dp[i][j][l][k]) % mod;
					}
		ans = (dp[n[2]][n[3]][n[4]][1] + dp[n[2]][n[3]][n[4]][2] + dp[n[2]][n[3]][n[4]][3]) % mod;
		return;
	}
}

T2

题面

$N$个二元组$(a_i,b_i)$，定义$c_1=a_1+b_1,c_i=b_i+\max⁡(c_{i−1},\sum\limits_{j=1}^{i}{a_j})$。现在你可以随意重排这$N$个二元组，求$c_N$的最小值。

zhx: 这题一看就贪心

万能贪心思路：考虑相邻的两个东西按照什么顺序来放

显然可以发现，$c_i$不严格单调递增

将$c_i$中的$b_i$放到$\max$里，那么$c_i=\max{(b_i+c_{i−1},b_i+\sum\limits_{j=1}^{i}{a_j})}$

我们令某一个$i$为$x$，$i+1$为$y$

那么较靠后的$c$值为，

$$\begin{align*} c_y&=\max{(b_y+c_{x},b_y+\sum\limits_{j=1}^{y}{a_j})}\\ &=\max{(b_y+b_x+\max{(c_{x-1}, \sum\limits_{j=1}^{x}{a_j})},b_y+\sum\limits_{j=1}^{y}{a_j})} \end{align*}$$

令$A=c_{x-1},B=\sum\limits_{j=1}^{x-1}{a_j}$，将里面的$\max$拆开

那么，

$$\begin{align*} c_y=\max{ \{b_x+b_y+A,a_x+b_x+b_y+B,a_x+a_y+b_y+B\} } \end{align*}$$

如果不交换，那么$c_y$就是上面式子

如果交换，

$$\begin{align*} c_y=\max{ \{b_x+b_y+A,a_y+b_x+b_y+B,a_x+a_y+b_x+B\} } \end{align*}$$

要满足后面最小，所以cmp的比较判断就是$\max{ \{b_x+b_y+A,a_x+b_x+b_y+B,a_x+a_y+b_y+B\} }<\max{ \{b_x+b_y+A,a_y+b_x+b_y+B,a_x+a_y+b_x+B\} }$

紧接着可以进行化简

由于小于号两边式子里都有$b_x+b_y+A$，对答案没有影响，可以删去，式子变成$\max{ \{a_x+b_x+b_y+B,a_x+a_y+b_y+B\} }<\max{ \{a_y+b_x+b_y+B,a_x+a_y+b_x+B\} }$

然后删去$B$，式子变成$\max{ \{a_x+b_x+b_y,a_x+a_y+b_y\} }<\max{ \{a_y+b_x+b_y,a_x+a_y+b_x\} }$

将$\max$里面相同的项提出来，式子变成$\max{ \{b_x,a_y\}+a_x+b_y}<\max{ \{b_y,a_x\}+a_y+b_x}$

移项，得$a_x+b_y-\max{ \{a_x,b_y\} }<a_y+b_x-\max{ \{a_y,b_x\} }$

两个数的和减去两个数中最大的，就是两个数中最小的

所以式子变成$\min{(a_x, b_y)}<min(a_y,b_x)$