[lg4401] [IOI2007] Miners

qwq(连续几篇qwq貌似不是很好qwq)

现有两个煤矿。

有三种类型的食品车。每当一个新的食品车到达煤矿时,矿工们就会比较这种新的食品和前两次(或者少于两次,如果前面运送食品的次数不足两次)的食品,并且:

  • 如果这几次食品车都是同一类型的食品,则矿工们产出一个单位的煤。
  • 如果这几次食品车中有两种不同类型的食品,则矿工们产出两个单位的煤。
  • 如果这几次食品车中有三种不同类型的食品,则矿工们产出三个单位的煤。

给出食品车的类型及其被配送的顺序,要求你写一个程序,确定哪个食品车应被送到煤矿1,哪个食品车应被送到煤矿2,以使得两个煤矿的产煤量的总和最大。

思路

把两个煤矿上两次的状态压成4维。滚动数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
inline void up(int &x,int y){if(x < y) x = y;}
const int N = 100010;
int n,a[N],f[2][4][4][4][4];
int C[26];
inline int getupper(){char c = getchar();while(!isupper(c)) c = getchar();return c;}
inline int calc(int u,int v,int w)
{
if(!v && !w) return 1;
if(!w) return 1 + (u != v);
if(u == v && v == w) return 1;
if(u != v && v != w && w != u) return 3;
return 2;
}
int main()
{
memset(C,0,sizeof(C));
C['M' - 'A'] = 1;C['F' - 'A'] = 2;C['B' - 'A'] = 3;
n = getint();
for(int i = 1;i <= n;i++) a[i] = C[getupper() - 'A'];
memset(f,-1,sizeof(f));
f[0][0][0][0][0] = 0;
for(int i = 1;i <= n;i++)
{
int now = a[i],u = i & 1,v = u ^ 1;
for(int j1 = 0;j1 < 4;j1++) for(int j2 = 0;j2 < 4;j2++) for(int k1 = 0;k1 < 4;k1++) for(int k2 = 0;k2 < 4;k2++)
{
if(!~f[v][j1][j2][k1][k2]) continue;
up(f[u][now][j1][k1][k2],f[v][j1][j2][k1][k2] + calc(now,j1,j2));
up(f[u][j1][j2][now][k1],f[v][j1][j2][k1][k2] + calc(now,k1,k2));
}
}
int sum = 0;
for(int j1 = 0;j1 < 4;j1++) for(int j2 = 0;j2 < 4;j2++) for(int k1 = 0;k1 < 4;k1++) for(int k2 = 0;k2 < 4;k2++) up(sum,f[n & 1][j1][j2][k1][k2]);
printf("%d\n",sum);
return 0;
}