题解 P7634 [COCI2010-2011#5] HONI

· · 题解

题目传送门

更好的阅读体验

算法分析：线性 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

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