简单DP计数训练

佚名 6年前 (2019-04-11) 随笔 1350人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

【计数DP】CodeForces - 474D Flowers

题目大意：

给定n,k，代表有n次询问和规定红花只能k朵连续地构造。现在有红花和白花两种颜色，问你构造出长度为n的满足条件的序列总共有多少种情况。

解题分析：
转移方程很好想，就是$dp[i]=dp[i-1]+dp[i-k]$，将拿红花的情况和拿白花的情况统计一下。但是因为会对$sum[i]$进行取模，所以$sum[r]$可能小于$sum[l]$，所以最后对输出的答案应该$+mod$。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define N int(1e5+5)
const int mod =  1e9+7;

ll dp[N+5],sum[N+5];

int main(){
    int n,k;cin>>n>>k;
    dp[0]=1;
    for(int i=1;i<k;i++)dp[i]=1,sum[i]=sum[i-1]+dp[i];
    for(int i=k;i<=N;i++){
        dp[i]=(dp[i-1]+dp[i-k])%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    while(n--){
        int l,r;scanf("%d%d",&l,&r);
        printf("%lld\n",(sum[r]-sum[l-1]+mod)%mod);
    }
}

View Code

【计数DP】Codeforces 1084 C. The Fair Nut and String

题目大意:

给你一个由小写字母组成的字符串 s ，让你找一种序列：

1、对于任意一个 i ，使得 s[ p[ i ] ] == 'a'

2、对于任意一个 i ，存在 p[ i ] < j < p[i + 1]，且s[ p[ i ] ] == 'b'

求这种序列有多少个，答案 mod 1e9

解题分析：

首先预处理字符串 S ，使得串中不存在除 a 、b 意外的字母且任意两个 b 不相邻，然后定义一个 last 变量存上一个 b 位置之前有多少序列，然后递推 dp：dp[ i ] = dp[ i - 1] + last + 1。

#include <bits/stdc++.h>
using namespace std;

string s;
string str="";
int dp[int(1e5+7)];
const int mod = 1e9+7;

int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]!='a'&&s[i]!='b')continue;
        if(i && s[i]=='b' && s[i-1]=='b')continue;
        str+=s[i];
    }//预处理原字符串
    int last=0;
    for(int i=0;i<str.size();i++){     //简单DP转移
        if(str[i]=='a')dp[i]=(dp[i-1]+last+1)%mod;
        else last=dp[i-1],dp[i]=dp[i-1];
    }
    printf("%d\n",dp[str.size()-1]%mod);
}