BZOJ-1806:|BZOJ-1806: [Ioi2007]Miners 矿工配餐 (DP题解)
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1806
思路:这是一道很裸的动态规划。确定状态f[i][a][b][c][d]表示送了第i次餐车后,第一个矿场的最后两次送餐是a,b第二个矿场的最后两次送餐是c,d,然后直接递推就可以啦。表示之前用了1000004^4的数组一直很奇葩的编译超时,后来直接写成滚动数组就A啦~*
【BZOJ-1806:|BZOJ-1806: [Ioi2007]Miners 矿工配餐 (DP题解)】代码:
#include #include #include using namespace std;
#define MAXN 100001 int f[2][4][4][4][4];
int n,t=0;
char s[MAXN];
int hash(char c){switch (c){case 'M':return 1;
case 'F':return 2;
case 'B':return 3;
}} int main(){memset(f,0,sizeof(f));
scanf("%d",&n);
scanf("%s",&s);
f[0][hash(s[0])][0][0][0]=f[0][0][0][hash(s[0])][0]=1;
for (int i=1;
i