对于给定的一个仅由A和B组成的字符串,通过选定从某一位置开始到结束的部分并执行剪切(Ctrl+X),然后粘贴(Ctrl+V)到该字符串的开始位置,使得形成的新字符串中连续的A数量sum最多,如何计算sum,给出C语言代码
时间: 2023-11-27 13:54:26 浏览: 54
可以采用动态规划的思想来解决这个问题。
设dp[i]为前i个位置中连续的A的数量sum最大值,则有:
- dp[i] = dp[i-1] + 1,如果第i个位置为A
- dp[i] = dp[j] * (i-j-1),其中j为i之前的某个位置,表示将[j+1,i]这一段剪切并粘贴到字符串开始位置后,产生的新字符串中连续的A数量为dp[j],而[i-j-1]表示除了[A]这一段的长度
最终的答案即为dp[n],其中n为字符串的长度。
以下是C语言代码实现:
```
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
char str[105];
scanf("%s", str);
int n = strlen(str);
int dp[105];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
if (str[i-1] == 'A') {
dp[i] = dp[i-1] + 1;
} else {
for (int j = 0; j < i-1; j++) {
dp[i] = max(dp[i], dp[j] * (i-j-1));
}
}
}
printf("%d\n", dp[n]);
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)