以前立志要跟鸡老师学dp，结果中途而废。隔了三个月然后这道1500的dp做不出来。。。
题目链接：http://codeforces.com/contest/877/problem/B 思路一：存a和b的前缀数目。 那我们可以枚举所有中间区间[i,j] a:[0-i] b:[i-j] a:[j-n] 把每个区间对应的值加起来。取最大值！妙啊！
#include <bits/stdc++.h> using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define for1(i,n) for(int i=1;i<=n;i++) #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) int a[5005],b[5005]; int main(){ IO; string s;cin>>s; int n = s.size(); forn(i,s.size()){ if(i) b[i+1] = b[i],a[i+1] = a[i]; if(s[i]=='b') b[i+1]++; else a[i+1]++; } int ans = 0; for1(i,n){ for(int j = i;j<=n;j++){ int x = b[j]-b[i-1]+a[i-1]+a[n]-a[j]; ans = max(x,ans); } } ans = max(ans,a[n]); cout <<ans<<'\n'; return 0; }思路二：dp 三个dp数组 0存的是a的最大长度 1存的是ab的最大长度 2存的是aba的最大长度
#include <bits/stdc++.h> using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define for1(i,n) for(int i=1;i<=n;i++) #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) int dp[5005][3]; int main(){ IO; string s;cin>>s; int n = s.size(); forn(i,n){ if(s[i]=='a'){ dp[i+1][0] = dp[i][0]+1; dp[i+1][1] = max(dp[i][1],dp[i][0]+1); dp[i+1][2] = max(dp[i][2]+1,dp[i][1]+1); } else{ dp[i+1][0] = dp[i][0]; dp[i+1][1] = max(dp[i][1]+1,dp[i][0]); dp[i+1][2] = max(dp[i][2],dp[i][1]+1); } } cout << max({dp[n][0],dp[n][1],dp[n][2]})<<'\n'; return 0; }