蓝桥杯真题 - 填充 - 题解
题目链接：https://www.lanqiao.cn/problems/3519/learning/
个人评价：难度 1 星（满星：5）
前置知识：动态规划
整体思路
- 设
d
p
[
i
]
dp[i]
dp[i] 表示到前
i
i
i 个字符能替换出最多的
00
,
11
00,11
00,11 子串个数，当第
i
−
1
i-1
i−1 与第
i
i
i 个字符至少有一个为
?或者两个字符相同时， d p [ i ] = d p [ i − 2 ] + 1 dp[i]=dp[i-2]+1 dp[i]=dp[i−2]+1，否则 d p [ i ] = d p [ i − 1 ] dp[i]=dp[i-1] dp[i]=dp[i−1]；
过题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000000 + 100;
int n;
char str[maxn];
int dp[maxn];
int main() {
#ifdef ExRoc
freopen("test.txt", "r", stdin);
#endif // ExRoc
ios::sync_with_stdio(false);
scanf("%s", str + 1);
n = strlen(str + 1);
for (int i = 2; i <= n; ++i) {
if (str[i] == '?' || str[i - 1] == '?' || str[i] == str[i - 1]) {
dp[i] = dp[i - 2] + 1;
} else {
dp[i] = dp[i - 1];
}
}
cout << dp[n] << endl;
return 0;
}
原文地址：https://blog.csdn.net/CSDNjiangshan/article/details/145330798
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！