题解：P7634 [COCI 2010/2011 #5] HONI

· · 题解

看错题卡了好久。。。

思路

显然有 dp。

设计一个 dp_{n,2}，dp_{i,1} 表示在第 i 个难度使用了 i\:\texttt{or}\:i+1 的题，dp_{i,0} 表示没用。

显然在 i 这个难度使用 i-1\:\texttt{or}\:i 的题对后面是没有影响的，所以把这种情况写进 dp_{i,0}。

先看更简单的 dp_{i,1}，对于 i 这个难度使用 i\:\texttt{or}\:i+1 的题不跟 i-1 的选择有关系，所以 dp_{i,1}=b_i\times (dp_{i-1,0}+dp_{i-1,1})。

再看 dp_{i,0}，这种情况分为两种：

  1. 使用固定 i 难度的题，情况数是 a_i\times(dp_{i-1,0}+dp_{i-1,1})。
  2. 使用 i-1\:\texttt{or}\:i 的题，假设 i-1 用的是 i-1\:\texttt{or}\:i 的题有 (b_{i-1}-1)\times dp_{i-1,1}，否则就是 b_{i-1}\times dp_{i-1,0}。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int i32;
#define int long long
#define debug() cout<<"come on"<<'\n'
#define mkp make_pair
#define pb push_back
#define ft first
#define sd second
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int mod=1e9+7;
int n,a[100005],b[100005],c[100005],dp[100005][2];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)cin>>b[i];
    dp[1][0]=a[1],dp[1][1]=b[1];
    for(int i=2;i<=n;i++){
        dp[i][0]=a[i]*(dp[i-1][1]+dp[i-1][0])+b[i-1]*dp[i-1][0]+(b[i-1]-1)*dp[i-1][1];
        dp[i][1]=b[i]*(dp[i-1][0]+dp[i-1][1]);
        dp[i][0]%=mod,dp[i][1]%=mod;
    }
    cout<<(dp[n][0]+dp[n][1])%mod;
}