【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=1806
【题意】
给定一个权在1..3内的序列，在保持相对位置不变的情况下拆分成两个序列，使获益最大。
【思路】
设f[i][a][b][c][d]表示前i个数，分给A的倒数两个为ab，分给B的倒数两个为cd，则有转移式：
f[i+1][b][x][c][d]<- f[i][a][b][c][d]+w(a,b,x)
f[i+1][a][b][d][x]<- f[i][a][b][c][d]+w(c,d,x)
其中x=s[i]，w为权值计算函数。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std; const int N = 1e5+; char s[N];
int n,f[][][][][]; int calc(int a,int b,int x)
{
int s=;
if(a) s++; if(b) s++;
if(a==b&&a) s--;
if(x==a) s--;
if(x==b&&a!=b) s--;
return s;
} int main()
{
scanf("%d%s",&n,s+);
int cur=;
memset(f[cur],0xef,sizeof(f[cur]));
f[cur][][][][]=;
FOR(i,,n) {
cur^=;
int x;
if(s[i]=='M') x=; else if(s[i]=='F') x=; else x=;
memset(f[cur],0xef,sizeof(f[cur]));
FOR(a,,) FOR(b,,) FOR(c,,) FOR(d,,) {
f[cur][b][x][c][d]=max(f[cur][b][x][c][d],f[cur^][a][b][c][d]+calc(a,b,x));
f[cur][a][b][d][x]=max(f[cur][a][b][d][x],f[cur^][a][b][c][d]+calc(c,d,x));
}
}
int ans=;
FOR(a,,) FOR(b,,) FOR(c,,) FOR(d,,)
ans=max(ans,f[cur][a][b][c][d]);
printf("%d\n",ans);
return ;
}