本文最后更新于:2020年4月11日 下午

题目分析

考虑一个类似于随机游走表的表,并将该表视为$+ y$方向上的(1-0的数量)和$-y$方向上的(0-1的数量)。

然后,在dp数组中,当(1-0)的最大值为$j$而(0-1)的最小值为$k$时,查找dp [i] [j] [k]:=该号码将被更新

到目前为止,在过渡中,很难将$y$坐标的上限值和下限值保持为点数。

无论考虑什么子序列,0的数目和1的数目之间的差必须等于或小于$K$,因此答案可能是$j + k <= K$的总和。下面的评论便容易理解。

$Code$

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
const int mod = 1e9 + 7;
//dp[i][j][k] := 动态规划数组、
//当-0的最大值为j且(0-1)的最小值为k时
ll dp[310][310][310];

int main(void){
    int N, K; cin >> N >> K;
    string s; cin >> s;
    dp[0][0][0] = 1;
    rep(i, N)rep(j, N + 1)rep(k, N + 1){
        if(dp[i][j][k] == 0) continue;

        if(s[i] == '1'){
            (dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k]) %= mod;
        }else if(s[i] == '0'){
            (dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k]) %= mod;
        }else{
            (dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k]) %= mod;
            (dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k]) %= mod;
        }
    }

    ll ans = 0;
    rep(i, N + 1)rep(j, N + 1){
        if(i + j <= K){//(1-0)的最大值与(0-1)的最大值之差应为K或更小。
            ans += dp[N][i][j];
            ans %= mod;
        }
    }

    printf("%lld\n", ans % mod);
    return 0;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT888 【ウサギとカメ】 上一篇
题解 AT1360 【双子とスイカ割り】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。