《自行车架》题目分析

这是一道比较复杂的DP题目。

首先我们观察题目数据，可以发现N、M和K都小于等于50，所以总共只有51^3大约是125000种情况。而Q的范围是100000，这提示我们应该预先把所有情况的答案都算出来保存在ans[51][51][51]里，遇到一个查询就直接输出。

那么怎么求ans[i][j][k]呢？ 考虑到这是一个多阶段的决策问题，我们首先想到的就是看看能不能DP。对于ans[i][j][k]，枚举最后一辆自行车是ABC哪种类型，转移到ans[i-1][j][k]、ans[i][j-1][k]和ans[i][j][k-1]这些状态上去。

遗憾的是我们仔细分析一下就会发现如果状态中只保存3种类型自行车的数量，是没办法确定转移的下一个状态的。

举个例子，比如我们知道ans[2][1][2]=7（题目中的例子），我们想在此基础上添加一辆B型车，那么这时ans[2][2][2]应该是多少呢？ 我们发现如果我们不知道最右的类型，我们就不能判断车架长度需要+2还是+3。

所以我们在状态中再加入两维，f[i][j][k][x][y]，表示i个A型，j个B型，k个C型，第一排最后一个是x型，第二排最后一个是y型（x和y的取值范围都是{A, B, C})，并且第一排长度大于第二排时车架的最短长度。

遗憾的是我们再仔细分析一下就会发现我们还是没办法确定转移的下一个状态。原因时我们不知道第二排最后一辆车距离第一排最后一辆车有多远。

于是我们在状态中再加入一维，f[i][j][k][x][y][d]，其中最后一维表示第一排和第二排最后一辆车的距离差。值得说明的是，d的取值范围只有{1, 2, 3}。d不能等于0，因为一个槽位同时只能有一侧停入自行车。d不会超过3，因为如果d大于等于4的话，我们一定可以把第一排最后一辆车放到第二排，使得总长度减少。

最终我们得到了一个5维的状态，这时总算是可以确定转移的下（上）一个状态了。

对于f[i][j][k][x][y][d]，我们最后添加的一辆车可能是第一排的的x型号，也可能是第二排的y型号；同时最后添加的车的左边那一辆可能有3种类型。所以总共f[i][j][k][x][y][d]的前驱状态有6个。

每个前驱状态的5维下标都是确定的，同时增加的车架长度也是确定的。大家可以自己动手计算一下，不再赘述。