滚动数组推一下就行.
- code:
- #include <bits/stdc++.h>
- #define setIO(s) freopen(s".in","r",stdin)
- using namespace std;
- int dp[2][4][4][4][4],n;
- char s[100004];
- int sub(int s)
- {
- if(s=='M') return 2;
- if(s=='F') return 3;
- return 1;
- }
- int val(int a,int b,int c)
- {
- int ret=1;
- if(a&&a!=b&&a!=c) ++ret;
- if(b&&b!=c) ++ret;
- return ret;
- }
- int main ()
- {
- // setIO("input");
- scanf("%d",&n);
- scanf("%s",s + 1);
- memset(dp,-1,sizeof(dp));
- dp[0][0][0][0][0] = 0;
- for (int i = 1;i <= n;i++)
- {
- for (int a1 = 0;a1 < 4;a1++)
- for (int a2 = 0;a2 < 4;a2++)
- for (int a3 = 0;a3 < 4;a3++)
- for (int a4 = 0;a4 < 4;a4++)
- {
- if (dp[(i + 1) % 2][a1][a2][a3][a4] == -1) continue;
- int b = sub(s[i]);
- dp[i % 2][a2][b][a3][a4]=max(dp[i % 2][a2][b][a3][a4],dp[(i + 1) % 2][a1][a2][a3][a4]+val(a1,a2,b));
- dp[i % 2][a1][a2][a4][b]=max(dp[i % 2][a1][a2][a4][b],dp[(i + 1) % 2][a1][a2][a3][a4] + val(a3,a4,b));
- }
- memset(dp[(i + 1) % 2],-1,sizeof(dp[(i + 1) % 2]));
- }
- int ans = 0;
- for (int a1 = 0;a1 < 4;a1++)
- for (int a2 = 0;a2 < 4;a2++)
- for (int a3 = 0;a3 < 4;a3++)
- for (int a4 = 0;a4 < 4;a4++)
- ans = max(ans,dp[n % 2][a1][a2][a3][a4]);
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3415855.html