题解 P7634 [COCI2010-2011#5] HONI

大佬教程收集整理的这篇文章主要介绍了题解 P7634 [COCI2010-2011#5] HONI，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题目传送门

算法分析：线性 dp

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

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

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

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

状态：

我们设计 (dp_{i,j}) 表示对于难度 (i) ，是用方法 (j) 解决的。其中 (jin{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=1end{Cases} ]

在此过程中，(i:2to 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

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

大佬总结

以上是大佬教程为你收集整理的题解 P7634 [COCI2010-2011#5] HONI全部内容，希望文章能够帮你解决题解 P7634 [COCI2010-2011#5] HONI所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。