《自信心》题目分析

本题最直接暴力的解法是枚举一个1~N的排列P作为学习能力值序列，然后根据题目规定计算自信心总和Sum(P)。

所有N!个Sum(P)中取最小值皆可。当然时间复杂度是O(N!)的，会超时。

本题中一个人的自信心只与周围5个人(包括自己)有关，这是一个比较明显的状态压缩DP的特征。

我们可以用f[i][j]表示前i个人的自信心已经确定，并且i-2, i-1, i, i+1, i+2这5个人的相对能力值序列是j的情况下，前i个人的最小信心总和。

注意这里j是一个1~5的排列。

f[i][j]可以通过枚举第i-3个人的相对能力值进行转移。这个思路的具体解法可以参考HiddenSouls的题解。

不过仔细算一下这个算法的时间复杂度处在超时边缘。代码不够优化，时间复杂度的常数稍微大一点就可能会超时。

进一步优化的思路在于优化j这一维的状态。我们不需要完整的这5个人的相对能力信息也可以进行计算。

比如可以用f[i][j]表示前i个人的自信心已经确定，并且i-1, i, i+1, i+2这4个人的相对能力值序列是j的情况下，前i个人的最小信心总和。

然后可以通过枚举第i-2个人的相对能力值，转移到f[i-1][k]。

这样状态数目就减少到之前的1/5。

出题人还有更优化的状态和转移。

TBD