先dp连续i个abc的最大得分,这样的思路有问题吗?
查看原帖
先dp连续i个abc的最大得分,这样的思路有问题吗?
541615
justin023楼主2024/11/8 15:30

先对连续i个abc的最大得分做dp,这样的思路为啥只过一小部分测试点呢,有大佬帮忙看看吗??

#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;
}

2024/11/8 15:30
加载中...