[vijos1386][bzoj1806]-[IOI2007]矿工配餐

题目（vijos）
题目（BZOJ）
我写的是记忆化搜索......不知道为什么bzoj上面TLE了......
用dp[step][a1][b1][a2][b2]表示搜索到第step个餐车时，第一个矿洞前两餐分别为a1,b1，第二个矿洞前两餐为a2,b2，
然后记忆化搜索过去就行。把b1换到a1位置，在b1位置换上新的餐车，第二个矿洞也是这样。
（但为什么bzoj上TLE了？！）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n;
char s[100005];
int p[100005];
int dp[100005][4][4][4][4];
inline int now(int x,int y,int z)
{
	if (!x && !y && z) return 1;
	if (!x && y && z && y!=z) return 2;
	if (!x && y && z && y==z) return 1;
	if (x!=y && x!=z && y!=z) return 3;
	if (x==y && z!=x) return 2;
	if (y==z && x!=z) return 2;
	if (x==z && y!=x) return 2;
	if (x==y && y==z) return 1;
}
int dfs(int step,int a1,int b1,int a2,int b2)
{
	if (step==n+1) return 0;
	if (dp[step][a1][b1][a2][b2]!=-1)
		return dp[step][a1][b1][a2][b2];
	int tmp=max(dfs(step+1,b1,p[step],a2,b2)+now(a1,b1,p[step]),dfs(step+1,a1,b1,b2,p[step])+now(a2,b2,p[step]));
	return dp[step][a1][b1][a2][b2]=tmp;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	memset(dp,-1,sizeof dp);
	for (register int i=1;i<=n;++i)
	{
		if (s[i]=='M') p[i]=1;
		else if (s[i]=='F') p[i]=2;
		else p[i]=3;
	}
	int ans=dfs(1,0,0,0,0);
	printf("%d",ans);
	return 0;
}

然后在bzoj上无论怎样常数优化都不行......
然后无奈去看了看题解......
啥？滚动数组？话说这复杂度和我的不是差不多吗。
后来才发现......
滚动数组是用来优化memset的时间复杂度的......

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n;
char s[100005];
int p[100005];
int dp[5][4][4][4][4];
int ans;
inline int now(int x,int y,int z)
{
    if (!x && !y && z) return 1;
    if (!x && y && z && y!=z) return 2;
    if (!x && y && z && y==z) return 1;
    if (x!=y && x!=z && y!=z) return 3;
    if (x==y && z!=x) return 2;
    if (y==z && x!=z) return 2;
    if (x==z && y!=x) return 2;
    if (x==y && y==z) return 1;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s);
    memset(dp,-1,sizeof dp);
    for (int i=0;i<n;++i)
    {
        if (s[i]=='M') p[i]=1;
        else if (s[i]=='F') p[i]=2;
        else p[i]=3;
    }
    dp[0][0][0][0][0]=0;
    for (int i=0;i<n;++i)
        for (int a1=0;a1<4;++a1)
            for (int b1=0;b1<4;++b1)
                for (int a2=0;a2<4;++a2)
                    for (int b2=0;b2<4;++b2)
                    {
                        int x=i%4,y=(i+1)%4;
                        if (dp[x][a1][b1][a2][b2]==-1) continue;
                        dp[y][b1][p[i]][a2][b2]=max(dp[y][b1][p[i]][a2][b2],dp[x][a1][b1][a2][b2]+now(a1,b1,p[i]));
                        dp[y][a1][b1][b2][p[i]]=max(dp[y][a1][b1][b2][p[i]],dp[x][a1][b1][a2][b2]+now(a2,b2,p[i]));
                    }
    for (int a1=0;a1<4;++a1)
        for (int b1=0;b1<4;++b1)
            for (int a2=0;a2<4;++a2)
                for (int b2=0;b2<4;++b2)
                    ans=max(ans,dp[n%4][a1][b1][a2][b2]);
    printf("%d",ans);
    return 0;
}