*【牛客 - 326B】背单词（线性dp）

60 阅读 0 评论 40 点赞

我是靠谱客的博主缓慢电脑，最近开发中收集的这篇文章主要介绍*【牛客 - 326B】背单词（线性dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题干：

winterzz1准备考4级了，现在winterzz1决定把世界上所有单词都背一遍，winterzz1发现任意一个单词最多有A个连续的元音，最多有B个连续的辅音。且单词最长长度为N，winterzz1问你在满打满算的情况他需要背多少单词？？？

输入描述:

首先输入一个T(T<=100)，表示有T组案例，每组案例依次输入三个正整数N,A,B，N<=5000,A<=50,B<=50;

输出描述:

输出winterzz1最多需要背多少单词，结果mod(10^9+7)

示例1

输入

复制

2
2 2 2
500 20 30

输出

复制

702
175540856

备注:

元音字母为a,e,i,o,u，其余21个字母均为辅音

解题报告：

这题不算难其实。。。dp[i][j][k]就完事了。。。不过超时了10多次后发现是因为mod运算了太多次了，，把mod改成const就火速AC了、、、好气啊、、不过可能是因为dp的姿势不太正确，，应该可以先记忆下来然后快速幂直接解决一下。。

这题抽象出来的意思就是：长度为n的01串，其中连续1的个数不能超过x个，连续0的个数不能超过y个。给定n,x,y，问能构造出多少合法串。。然后再加强一下：对0和1，有两个对应的权值，，这就变成这道题了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<ctime>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll dp[5005][2][55];//0代表元音，1代表辅音
const ll mod = 1e9+7;
int n,a,b;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d",&n,&a,&b);
        int up = max(a,b);
        for(int i = 0; i<=n; i++) {
            for(int j = 0; j<=50; j++) {
                    dp[i][0][j]=dp[i][1][j]=0;//别只初始化到up，，因为有可能上次的up更大，所以没有初始化完全。。。
            }
        }
        if(n == 1) {
            puts("26");continue;
        }
        dp[1][0][1]=5;
        dp[1][1][1]=21;
        for(int i = 2; i<=n; i++) {
            //更新元音的
            for(int j = 1; j<=min(i-1,b); j++) dp[i][0][1] = (dp[i][0][1] + dp[i-1][1][j]*5ll%mod)%mod;
             
            for(int j = 2; j<=min(i,a); j++) dp[i][0][j] += dp[i-1][0][j-1]*5%mod;
            //更新辅音的
            for(int j = 1; j<=min(i-1,a); j++) dp[i][1][1] = (dp[i][1][1]+dp[i-1][0][j]*21%mod)%mod;
             
            for(int j = 2; j<=min(i,b); j++) dp[i][1][j] += dp[i-1][1][j-1]*21%mod;
        }
        ll ans = 0;
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=50; j++) {
                if(j <= a) ans = (ans + dp[i][0][j])%mod;
                if(j <= b) ans = (ans + dp[i][1][j])%mod;
            }
        }
        printf("%lldn",ans);
    }
    return 0 ;
 }
/*
2
2 2 2
500 20 30
*/

还有一个10msAC的代码，（以后再补一下吧、、）：

（这个代码大概意思就是先dp[i][j]算出所有的，再减去连续a个元音的，或者连续b个辅音的，，也不算难想到啊其实，不知道比赛的时候在干什么。。唉可能还是自己苔菜了、、）

#include<bits/stdc++.h>
using namespace std;
using LL=unsigned long long;
const int M=6e3+5;
const int mo=1e9+7;
LL dp[M][2],cnt[M];
LL qpow(LL a,LL b)
{
    LL res=1;
    while(b>0)
    {
        if(b&1)
            res=res*a%mo;
        b>>=1;
        a=a*a%mo;
    }
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d%d%d",&n,&a,&b);
        for(int i=1;i<=n;i++)
            dp[i][0]=dp[i][1]=0;
        dp[0][0]=dp[0][1]=1;
        dp[1][0]=5;
        dp[1][1]=21;
        cnt[1]=26;
        LL pa=qpow(5,a+1),pb=qpow(21,b+1),res=26;
       // cout<<pa<<"=="<<pb<<endl;
        for(int i=2;i<=n;i++)
        {
            dp[i][0]=5*cnt[i-1]%mo;
            dp[i][1]=21*cnt[i-1]%mo;
            if(i>a)
                dp[i][0]=(dp[i][0]-dp[i-a-1][1]*pa%mo+mo)%mo;
            if(i>b)
                dp[i][1]=(dp[i][1]-dp[i-b-1][0]*pb%mo+mo)%mo;
            cnt[i]=(dp[i][0]+dp[i][1])%mo;
            res=(cnt[i]+res)%mo;
        }
        printf("%lldn",res);
    }
 
    return 0;
}