P1180 - 礦工配餐
From Admin Normal (OI)
總時限：16s 內存限制：128MB 代碼長度限制：64KB
描述 Description
現有兩個煤礦，每個煤礦都雇用一組礦工。采煤工作很辛苦，所以礦工們需要良好飲食。每當一輛食品車到達煤礦時，礦工們便會產出一定數量的煤。有三種類型的食品車：肉車，魚車和面包車。
礦工們喜歡變化的食譜。如果提供的食品能夠不斷變化，他們的產煤量將會增加。每當一個新的食品車到達煤礦時，礦工們就會比較這種新的食品和前兩次（或者少於兩次，如果前面運送食品的次數不足兩次）的食品，並且：
如果這幾次食品車都是同一類型的食品，則礦工們產出一個單位的煤。
如果這幾次食品車中有兩種不同類型的食品，則礦工們產出兩個單位的煤。
如果這幾次食品車中有三種不同類型的食品，則礦工們產出三個單位的煤。
預先已知食品車的類型及其被配送的順序。通過確定哪車食品送到哪個煤礦可以影響產煤量。食品車不能被拆分，每個食品車必須被全部送到一個或另一個煤礦。兩個煤礦也並不要求接收相同數量的食品車（事實上，也允許將所有食品車都送到一個煤礦）。
任務
給出食品車的類型及其被配送的順序，要求你寫一個程序，確定哪個食品車應被送到煤礦1，哪個食品車應被送到煤礦2，以使得兩個煤礦的產煤量的總和最大。
輸入格式 InputFormat www.2cto.com
輸入的第一行包含一個整數N (1 ≤ N ≤ 100 000), 表示食品車的數目。
第二行包含一個由N個字符組成的字符串，按照配送順序依次表示食品車配送的食品的類型。每個字符是以下三個大寫字母之一：'M' (表示肉類), 'F' (表示魚類) 或 'B' (表示面包)。
輸出格式 OutputFormat
輸出一個整數，表示最大的總產煤量。
樣例輸入 SampleInput [復制數據]
樣例輸入1
6
MBMFFB
樣例輸入2
16
MMBMBBBBMMMMMBMB
樣例輸出 SampleOutput [復制數據]
樣例輸出1
12
樣例輸入2
29
數據范圍和注釋 Hint
在樣例1中，可以按照如下的順序運送食品車：煤礦 1, 煤礦 1, 煤礦 2, 煤礦 2, 煤礦 1, 煤礦 2, 依次產生的產煤量為1, 2, 1, 2, 3 和 3 個單位，一共是12 個單位。還有其它運送方式也能產生上述最大總和的產煤量。
時間限制 TimeLimitation
前10點時限1s,分值8分
後2點時限3s,分值10分
這題看著就是不可解的。
但是仔細觀察會發現它的情況較少，分支巨多（2^N）？？
於是我們用滾動數組+Dp顯然可以用F[i][j][k][l][m]表示子結構
j,k,l,m為2個礦工最近2次的伙食（0表示沒有）
任何坑爹的題目先想想能不能Dp……
記憶化搜索不能滾動還會爆棧，於是Dp的存在性證畢。
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define NDEBUG
int n,a[MAXN];
int f[2][4][4][4][4]; //1->M 2->F 3->B
int cost[4][4][4]={0};
int _cost(int i,int j,int k)
{
if (k==0) return 0;
if (i==0) i=k;
if (j==0) j=k;
if (i!=j&&i!=k&&j!=k) return 3;
if (i!=j||i!=k||j!=k) return 2;
return 1;
}
int main()
{
#ifndef NDEBUG
freopen("Vijos1386.in","r",stdin);
#endif
scanf("%d",&n);getchar();
for (int i=0;i<n;i++)
{
switch (getchar())
{
case 'M':a[i]=1;break;
case 'F':a[i]=2;break;
case 'B':a[i]=3;break;
}
}
for (int i=0;i<=3;i++)
for (int j=0;j<=3;j++)
for (int k=0;k<=3;k++)
{
cost[i][j][k]=_cost(i,j,k);
#ifndef NDEBUG
cout<<i<<' '<<j<<' '<<k<<':'<<cost[i][j][k]<<endl;
#endif
}
memset(f,128,sizeof(f));
f[0][0][0][0][0]=0;
for (int ii=0;ii<n;ii++)
{
int i=ii%2;
for (int j=0;j<=3;j++)
for (int k=0;k<=3;k++)
for (int l=0;l<=3;l++)
for (int m=0;m<=3;m++)
{
if (f[i][j][k][l][m]>=0)
{
f[i^1][k][a[ii]][l][m]=max(f[i^1][k][a[ii]][l][m],f[i][j][k][l][m]+cost[j][k][a[ii]]);
f[i^1][j][k][m][a[ii]]=max(f[i^1][j][k][m][a[ii]],f[i][j][k][l][m]+cost[l][m][a[ii]]);
}
}
}
int ii=n%2,ans=0;
for (int j=0;j<=3;j++)
for (int k=0;k<=3;k++)
for (int l=0;l<=3;l++)
for (int m=0;m<=3;m++)
ans=max(ans,f[ii][j][k][l][m]);
cout<<ans<<endl;
return 0;
}
