【算法学习笔记】42.正反DP 填充连续 SJTU OJ 1285 时晴时雨

浏览数：23 / 时间：2015年06月08日

Description

Taring 喜欢晴天，也喜欢雨天。

Taring说：我想体验连续的K天的晴朗，去远足，去放歌；我还想再这K个晴天之后，再去体验连续的K天的云雨，去感受落雨时的轻语。这是令Taring最开心的事情了。其它的时间，Taring会在机房默默的编写着代码。

当然，Taring不想在这连续的K个晴天和连续的K个雨天里被机房的事务打扰或者被自然天气的变化中断。也就是说，这K个晴天和K个雨天必须是连续的，但是他们之间并不需要时间连续。显然的，Taring如果在感受了连续的K天晴朗后，前去机房写代码，等待下雨的时候再次开始他的感悟，这样是不会影响Taring的心情的。

Taring通过天气预报得到了最近连续 N 天中若干天的天气情况（天气情况只有“晴”和“雨”两种），但其他的天数的天气情况均是未知的。

他想知道有多少种可能的不同的天气情况（对于两种天气情况，如果有任意一天的天气情况是不一样的，就算做不同的天气情况），使他能够完成这两项体验。

Input Format

输入共有两行。

第1行有2个整数，分别表示上文中所述的N和K。

第2行是一个长度为N的字符串，仅包含有B（清），W（雨），X（未知）三种字符。

Output Format

输出一个整数Ans，表示合法的天气方案数量。

由于Ans可能很大，请将答案Mod 1,000,000,007

Sample Input 1

4 2
XXXX

Sample Output 1

Sample Input 2

10 2
XXBXXWXXXX

Sample Output 2

原题:http://codeforces.com/contest/204/problem/D

官方题解:http://codeforces.com/blog/entry/4849

根据官方题解分析大致思路如下:

//b[i] 顺序DP 表示到i位置为止没有出现k个连续的B的填充方法数

//c[i] 顺序DP 表示到i位置位置恰好第一次出现连续k个B的填充方法数

//w_1[i] 逆序DP 表示从n开始到i位置没有出现k个连续的W的填充方法数

//w_2[i] 逆序DP 表示从n开始到i位置出现了k个连续的W填充方法数

//total[i] 逆序DP 表示从n位置开始到i位置结束时一共有多少种填充方法

第1步求b[]

　　首先初始化 b[0] = 1; 还有S[0]=‘0‘;//这一步是为了以后的判断比较方便

　　1.1 判断当前处理位置的类型

　　1.1.1 如果遇到不确定位 X ,则让b[i]= 2 * b[i-1] 因为此处可以有两种填充方法, 当然可能会产生一些错误的填充下面进行处理

　　1.1.2 如果遇到的是确定位则让b[i] = 1 * b[i-1] 因为只有一种填充方法, 当然也会产生一些错误的填充

　　1.2 记录当前位置连续的B的个数 continous_b[i]

　　1.3 如果 continous_b[i]>=k 和 S[i-k]不是‘B‘

//来计算错误的填充数目 bad

//由于是DP过程,我们假设b[0]~b[i-1]的计算都是正确的, 则错误的填充指的是从i-k开始到 i位置恰好是连续k个B的情况

//根据样例则是 xxxxxWBB 的情况, 前面的xxxxx的填充数就是 b[i-k-1] 后面的WBB是固定的部分 * 1

　　　　所以 bad = 1 * b[i-k-1]

　　　　(注意特殊情况如果i=k 也就是恰好前k个字符可以实现k个B的情况, 则让bad为1即可)

　　最后让 b[i] = b[i] - bad;

第2步求c[]

　　2.1 c[0]=0

　　2.2 c[i] 其实就是第1步里的bad 不同之处就是如果不满足那个情况则要另c[i]=0

　　//如果把c[]的计算和b[]的融合在一起则不需要continous_b数组只需要一个数即可

第3步求w_1[]

　　和第1步一样的思想,不同的方向而已

第4步求total[]

　　逆序遇到X则累成2

第5步求w_2[]

　　把total和w_1相减即可 //补集的思想

第6部求最终结果ans

　　这里要注意: 我们已经得到了c[]和w[], c[]表示在i位置处第一次出现连续k个B的填充方法数目, w[]表示后j个中出现连续k个W的方法数目,可见这要遍历i从1到n

　　ans += c[i] * w[i+1]即可,原因在于 c[]已经完成了去重的工作!

PS: mod时,有一个细节要注意就是减法的取模要先加一个mod再取模, 原因:余数之间的减法操作可能会导致负数的存在!

代码如下:

#include <iostream>
using namespace std;

const int MaxN = (int) 1e6+5;
const int Mod = (int) 1e9+7;
typedef unsigned long long ULL;
char S[MaxN];
ULL b[MaxN],c[MaxN],w[MaxN],continous_b[MaxN],total[MaxN];
//continous_b记录的是到i位置时 恰好出现了连续的k个B的情况数目 不用也行

int main(int argc, char const *argv[])
{
    int n,k; cin>>n>>k;
    S[0]=‘0‘;//为了在计算b的时候 临界情况的判断
    cin>>(S+1);//为了下标对齐,从1开始输入

    //求b[] b[i]表示的是 从1开始到i位置 没有出现过连续的k个B的情况的个数
    b[0] = 1;
    
    for (int i = 1; i <= n; ++i)
    {
        
        //如果是X 由于可以填2种 所以乘2 注意:此时的b[i]是有bad filling的 
        //这个bad filling就是指, 前i个位置 有连续k个B
        //假设之前的b 全是正确的 那么这个bad filling 只有一种情况 那就是刚好填了B且满足前k个都是B
        b[i] = ( S[i]==‘X‘ ) ? 2 * b[i-1] % Mod : 1 * b[i-1]; 
        continous_b[0]=0;
        //为了找出是否此时出现了 bad filling 我们要记录到i为止 前面出现的连续的B的个数
        switch(S[i]){
            case ‘X‘:
            case ‘B‘: // 可继
                continous_b[i] = continous_b[i-1]+1;
                break;
            case ‘W‘: //断了
                continous_b[i] = 0;
                continue;//可以下一次循环了 因为肯定不是bad filling
        }
        //判断是否出现了bad filling 
        if(continous_b[i] >= k and S[i-k]!=‘B‘){ //正好出现了连续的k个B
            //此处 右边的 1 * b[i-k-1] 中的1表示的是WBB的情况:只有一种,b[i-k-1]表示的是前i-k-1中没有连续k个B的情况
            //##### 重点 : 两者相乘就是所谓的bad fillings 
            int bad ;
            if (i > k){
                bad = 1 * b[i-(k+1)];
            }else if(i==k){
                bad = 1 * 1;//特殊临界情况
            }
            
            c[i] = i-k-1>=0 ? b[i-k-1] : 1 ;

            b[i] = (b[i] - bad + Mod) % Mod; 
        }else
            c[i] = 0;
    }//此时已经计算了 b[]和continous_b[]

    //求c[] ci表示的是到第i个位置 恰好出现了连续的k个B的情况数 (目的是为了去重) 也可以放在上一个循环里面做
    // c[0] = 0;
    // for (int i = 1; i <= n; ++i)
    // {
    //     if(continous_b[i]>=k and S[i-k]!=‘B‘)
    //         c[i] = i-k-1>=0 ? b[i-k-1] : 1 ;
    //     else
    //         c[i] = 0;
    // }


    //现在求w[i], w[i]表示的是从最后一个位置开始 到i截止 有k个连续的W的情况数 和第一步类似 最后加上一部补就好了

    //现在的w[i]还不是真正的结果
    w[n+2] = 1;//为了方便
    w[n+1] = 1;
    S[n+1] = ‘0‘;
    int continous_w = 0;
    for (int i = n; i >=0; --i)
    {
        w[i] = (S[i]==‘X‘) ? 2 * w[i+1] % Mod : w[i+1];
        switch(S[i]){
            case ‘X‘:
            case ‘W‘:
                continous_w++;
                break;
            case ‘B‘:
                continous_w = 0;
                continue;//不用判断是否有bad fullings了
        }

        if(continous_w >= k and S[i+k] != ‘W‘)
            w[i] = (w[i] - w[i+k+1] + Mod) % Mod;
    }

    //记录全部情况的数量
    total[n+1]=1;
    for (int i = n; i >=0; --i) {
        total[i] = (S[i]==‘X‘) ? 2 * total[i+1] % Mod : total[i+1];
    }
    
    //变换为补集
    for (int i = 1; i <= n; ++i)
        w[i] = (total[i] - w[i] + Mod) % Mod;    
    

    ULL ans = 0;
    for (int i = 1; i <= n-1; ++i){ 
        ans = (ans + c[i] * w[i+1]) % Mod;
    }
    cout<<ans<<endl; 
    
    // for (int i = 1; i <= n; ++i)
    // {
    //     cout<<b[i]<<" ";
    // }cout<<endl;

    // for (int i = 1; i <= n; ++i)
    // {
    //     cout<<c[i]<<" ";
    // }cout<<endl;
     // for (int i = 1; i <= n; ++i)
    // {
    //     cout<<w[i]<<" ";
    // }cout<<endl;
    return 0;
}
/*
10 2
XXBXXWXXXX
        3 2
*/