在这里插入图片描述
UVA1379
定义：
$Map[i][j]$为对战第$i$支队伍时，胜率排名第$j$位的棒球手的胜率
$Schedule[i]$为第$i$天的对手
$dp[i][a][b][c][d]$为考虑到前$i$天时，第$i$天派出胜率排名第$a$位，第$i-1$天派出第$b$位，第$i-2$天派出第$c$位，第$i-3$天派出第$d$位选手时的最大期望值。因为选手比赛后需要$Reset$至少4天，所以需要4天的派遣情况才能去重并使状态唯一。
转移方程：

如果第$i$天有比赛，则枚举第$i$个人应该派遣谁，并选取由最优的子状态转移过来。（因为选手休息4天又能上场了，所以枚举到排名第5就可以了。比如选手$A$第一天上场，然后第二到五天休息，第六天又能重新上场了，一到五天五个人）。如果第i天没有比赛，则以$dp[i][0]$存储$dp[i-1]$中的最优状态。
去重：
为了防止选手在5天内重复上场，在每考虑第i场比赛的人选时，要保证第i场比赛的选手在第$i-1，i-2，i-3，i-4$场比赛中未出场过。定义$GetPitcher(Opponent, Index)$返回在面对编号为$Opponent$的对手时，排名第$Index$的选手的$ID$。去重详见代码。
滚动数组优化：
这道题的空间卡的严，如果定义$dp[211][6][6][6][6]$会爆空间，因此需要优化。可以发现$dp$中不是$i$就是$i-1$，明显的滚动数组优化。
AC代码：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
constexpr static int inf = 0x3f3f3f3f;
int N, M, G, D;
struct Node{
	int ID, Val;
	bool operator<(const Node& Right)const {
		return this->Val > Right.Val;
	}
}Map[101][101];
int Schedule[211];
int dp[2][6][6][6][6];
void Input() {
	scanf("%d%d%d", &N, &M, &G);
	for (int i = 1; i <= M; ++i) {
		for (int j = 1; j <= N; ++j) {
			scanf("%d", &Map[i][j].Val);
			//记录选手ID，用于去重
			Map[i][j].ID = j;
		}
		//将面对第i名对手时的选手按胜率降序排列
		sort(Map[i] + 1, Map[i] + N + 1);
	}
	D = G + 10;
	for (int i = 1; i <= D; ++i) {
		scanf("%d", &Schedule[i]);
	}
	return;
}
//如果Index是0，返回一个不存在的ID，使循环继续
int GetPitcher(int Opponent, int Index) {
	if (!Index) {
		return 0;
	}
	return Map[Opponent][Index].ID;
}
double DP() {
	memset(dp[0], 0x0, sizeof(dp[0]));
	for (int i = 1; i <= D; ++i) {
		int
			&& Cur = i & 1,//等价于i
			&& Pre = 1 - Cur;//等价于i-1

		memset(dp[Cur], 0x0, sizeof(dp[Cur]));
		if (Schedule[i]) {
			for (int a = 1; a <= 5; ++a) {
				for (int b = 0; b <= 5; ++b) {
					//如果第i场比赛派第a名选手，那就不能和第i-1场比赛时决定的第b名选手ID相同，即去重
					if (i > 1 && GetPitcher(Schedule[i], a) == GetPitcher(Schedule[i - 1], b)) {
						continue;
					}
					for (int c = 0; c <= 5; ++c) {
						if (i > 2 && GetPitcher(Schedule[i], a) == GetPitcher(Schedule[i - 2], c)) {
							continue;
						}
						for(int d = 0; d <= 5; ++d) {
							if (i > 3 && GetPitcher(Schedule[i], a) == GetPitcher(Schedule[i - 3], d)) {
								continue;
							}
							for (int e = 0; e <= 5; ++e) {
								if (i > 4 && 
									GetPitcher(Schedule[i], a) == GetPitcher(Schedule[i - 4], e)) {
									continue;
								}
								dp[Cur][a][b][c][d] = max(
									dp[Cur][a][b][c][d], 
									dp[Pre][b][c][d][e] + Map[Schedule[i]][a].Val
								);
							}
						}
					}
				}
			}
		}
		else {
			for (int a = 0; a <= 5; ++a) {
				for (int b = 0; b <= 5; ++b) {
					for (int c = 0; c <= 5; ++c) {
						for (int d = 0; d <= 5; ++d) {
							dp[Cur][0][a][b][c] = max(
								dp[Cur][0][a][b][c], 
								dp[Pre][a][b][c][d]
							);
						}
					}
				}
			}
		}
	}
	int
		&& Ans = 0, 
		&& Cur = D & 1;
	for (int a = 0; a <= 5; ++a) {
		for (int b = 0; b <= 5; ++b) {
			for (int c = 0; c <= 5; ++c) {
				for (int d = 0; d <= 5; ++d) {
					Ans = max(Ans, dp[Cur][a][b][c][d]);
				}
			}
		}
	}
	return Ans / 100.;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		Input();
		printf("%.2lf\n", DP());
	}
	return 0;
}