今天是dp喵，简单喵~想象一下，本喵在字符串里寻找“Cwbc”这四个字符组成的序列（不区分大小写哦~）。代码里用四个变量来跟踪本喵找到了多少种“半成品”序列：dp0：记录找到的 'c' 开头数量（这是第一步喵~）dp1：记录找到的 'cw' 组合数量（已经有点完整的雏形啦！）dp2：记录找到的 'c
展开全文
这道题需要格外注意一句话：
不区分大小写。
所以考虑设 dpi,0/1/2/3dp_{i,0/1/2/3}dpi,0/1/2/3 表示以 iii 结尾，最后一位恰好匹配到 cwbc 的第 0/1/2/30/1/2/30/1/2/3 个字符的方案数。
然后稍微压一下状态，写出状态转移方程：（代码
展开全文
import sys
MOD = 2000120420010122
for line in sys.stdin:
a = line.strip().lower()
ans = 0
c = 0
cw = 0
cwb = 0
for x in a:
展开全文
dp数组的含义：匹配到子串当前位置的子序列的个数。也就是说dp[2]意思是匹配到'b'这个字符的子序列个数是多少，匹配到b，那么前面一定是有cw的，所以当前dp[2]+=dp[1]状态转移方程为：dp[i]+=dp[i-1]但是注意若当前字符与前面有字符相同，也就是这里判断到c时dp[0]要继续自增
展开全文
还是挺典的一个子序列动态规划的，就是用dp[i]表示以Cwbc中第i个位置结尾的子序列个数就好了
唯一要注意的点是这里不区分大小写
// BggBB wZPXsv:. UBgQGv
// BgEQQ
展开全文
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 200012042
展开全文
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5, M = 2000120420010122;
ll f[N];
int main() {
ios::s
展开全文
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=2000120420010122;
void solv
展开全文
//算法学习第四题，DP
#include <bits/stdc++.h>
using namespace std;
//using ll=long long;
const long long MOD = 2000120420010122;
//int 最大只有 $2 \times 1
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
