社区讨论
先dp连续i个abc的最大得分,这样的思路有问题吗?
P10721[GESP202406 六级] 计算得分参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @m38f48ze
- 此快照首次捕获于
- 2024/11/08 15:31 去年
- 此快照最后确认于
- 2025/11/04 15:08 4 个月前
先对连续i个abc的最大得分做dp,这样的思路为啥只过一小部分测试点呢,有大佬帮忙看看吗??
C#include<bits/stdc++.h>
using namespace std;
int dp[30]; //dp[i]表示连续i个子串abc的最大得分
int a[30];//得分序列
int n,m; //长度为n的得分序列 ,字符串长度为m
string s;//字符串
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> m;
cin >> s;
//2 3 1 1 12 1 1
//2 4 6 8 12 14 16
//dp[5] = dp[3] + dp[2]
for(int i = 1; i <= n; i++){
dp[i] = a[i];
for(int j = 1; j < i; j++){
dp[i] = max(dp[i] , dp[j] + dp[i - j]);
}
}
//dabcabcabcabz
long long sum = 0;//总分
int cnt = 0;//连续个数
for(int i = 0; i < s.size() - 2; i++){
if(s[i] == 'a' && s[i + 1] == 'b' && s[i + 2] == 'c'){
cnt++;
i = i + 2;
}else{
sum += dp[cnt]; //即使cnt为0,dp[0] = 0,不影响
cnt = 0;
}
}
//dabcabcabcabc 防止最后一个是abc , for循环最后执行的是if语句就结束了
sum += dp[cnt];
cout << sum;
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...