自动搬运

查看原文

来自洛谷，原作者为

	☯☯枫☯☯ Why son code is not called daughter code?

搬运于2025-08-24 22:31:45，当前版本为作者最后更新于2021-06-27 16:22:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

更好的阅读体验

算法分析：线性 dp

应该来说是比较明显的线性 dp，关键在于如何设计状态及转移方程。

在本题中涉及两种“题目”，即仅能被视为一个难度的“题目”和能被视为有两个连续难度的“题目”。作为两种不同的情况，一维的 dp 明显是不够的，需要加入第二维。

为了表述方便，下文称“仅能被视为一个难度的‘题目’”为“第一种题目”，其数量记为 $a_i$；称“能被视为有两个连续难度的‘题目’”为“第二种题目”，其数量记为 $b_i$。在分析中，将省略“取模”这一过程。

接下来分析 dp 的状态及转移方程。

状态：

我们设计 $dp_{i,j}$ 表示对于难度 $i$ ，是用方法 $j$ 解决的。其中 $j\in\{0,1\}$，在此记 $j=0$ 为使用了第一种题目，$j=1$ 为使用了第二种题目（当然，反过来也一样）。

边界：

根据状态，显然地，$dp_{1,0}=a_1,dp_{1,1}=b_1$，要求的答案为 $dp_{n,0}+dp_{n,1}$

转移方程：

• 根据题意，对于 $j=0$ 的情况，要考虑难度 $i-1$ 的使用情况。若上一个使用了第一种题目，那么其贡献为 $dp_{i-1,0}\times(a_i+b_{i-1})$，若上一个使用了相应的第二种题目，则贡献为 $dp_{i-1,1}\times(a_i+\max(b_{i-1}-1,0))$。由于上一个使用了第二种题目，数量须 $-1$。同时为了防止 $b_{i-1}=0$ 的情况，与 $0$ 取最大值，增强程序的容错率。

• 对于$j=1$ 的情况较为简单，两种情况的贡献各为 $dp_{i-1,0}\times b_i$ 以及 $dp_{i-1,1}\times b_i$。

  综上所述，有：

  $$dp_{i,j}=\begin{cases}dp_{i-1,0}\times(a_i+b_{i-1})+dp_{i-1,1}\times(a_i+\max(b_{i-1}-1,0))&j=0\\dp_{i-1,0}\times b_i+dp_{i-1,1}\times b_i&j=1\end{cases} $$

在此过程中，$i:2\to n$，时间复杂度为 $\mathcal{O}(n)$，满足条件。

下面给出代码：

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=a;i<=b;++i)
using namespace std;
inline int read();
const int N=1e5+10,mod=1e9+7;
int n,a[N],b[N];
ll dp[N][2];
int main() {
	n=read();
	F(i,1,n)a[i]=read();
	F(i,1,n-1)b[i]=read();
	dp[1][0]=a[1],dp[1][1]=b[1];
	//初始化 
	F(i,2,n){
		dp[i][0]=(dp[i-1][0]*(a[i]+b[i-1])+dp[i-1][1]*(a[i]+max(b[i-1]-1,0)))%mod;
		dp[i][1]=(dp[i-1][0]*b[i]+dp[i-1][1]*b[i])%mod;
	}//转移 
	printf("%lld",(dp[n][0]+dp[n][1])%mod);
	return 0;
}
inline int read() {
	reg int x=0;
	reg char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

写到这里已经足够了，但事实上，空间仍然可以优化。观察到 $dp_{i,0}$ 和 $dp_{i,1}$ 均由 $dp_{i-1,0}$ 和 $dp_{i-1,1}$ 迭代转移过来，因此可以用一个变量来滚动记录。下面给出利用变量滚动记录的代码：

	x=a[1],y=b[1];
	F(i,2,n){
		ll xx=(x*(a[i]+b[i-1])+y*(a[i]+max(0,b[i-1]-1)))%mod;
		ll yy=(x*b[i]+y*b[i])%mod;
        //滚动
		x=xx,y=yy;
	}

两个代码在本质上是完全一致的。

AC

欢迎交流讨论，请点个赞哦~