题源：https://vjudge.net/problem/UVA-1379
这篇博文是来质疑这道题及网上大多数的解法的。读者可以先行阅读其他题解。
开始我想到了与大多数解法相同的思路（虽然是在紫书的提示下），但随后予以了否定。此处先不表述思路，先以实例为证。实话说在未构造出这组数据前，我还未敢妄下断言质疑题解。
1 6 7 7 10 10 10 10 90 10 90 10 10 10 10 10 10 90 10 10 10 10 10 10 90 10 10 10 10 10 10 90 10 10 10 10 10 10 10 10 10 10 10 10 90 10 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 0
经测试，只考虑前5名的代码这组数据的结果是4.70。各位读者也可自行验证。
但实际上，若按照天数顺序取5,1,2,3,4,6,5, 最优解应该是5.5。
接下来解释我认为取前5名错误的原因。首先是这种解法忽略了很重要的一点，那就是存在与第5名并列的情况，这也是构造这组数据的出发点，即让5、6号投手在第6个对手并列，而实际上在遇到第6个投手时取6号才为最优解。至此已经验证该解法错误。
上述思路是我第一次排除该解法的原因，同时也让我坚定这种解法是错误的。其次经过更深入的思考，反例远不止有并列这么简单，事实上如果5、6、7...差距很小（比如只有1），但后续5会阻碍非常大的胜率的选择（比如99），同样也不能得到最优解。其实问题并不在局部最优解和最优子结构问题上，而是在转移方程上。转移方程隐式限定了前面的选择都局限于前5，但却忽略了可以选6、7的情况，这是错误的根本原因。
关于正解，我这里只能给出我认为的正解与思路，如有错误还请指出。
我们假设已经得到了最优解，每天选的投手为ai。此时单独看某一特定天投手的选择，现在影响该天的选择只有前4天和后4天的选择，前4天不用解释；也不难理解后4天选择的投手该天一样不能选择。那么在极端情况下，假设这8天选择的投手各不相同，并且分别为该天相对对手胜率的1-8名，那么我们可以得出该天选择的最坏情况是第9名。这样我的解法就是将每一步的选择范围拓展为前9名，其它与基本解法保持一致。
同时经过测试，我的代码跑上面的数据结果为5.5，读者也可进行测试。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> //#define fre #define DEBUG using namespace std; const int maxn = 10005; int dp[315][maxn], powtn[5], op[315]; struct Node { int i, p; bool operator< (const Node &b) const { return p > b.p; } } perct[105][205]; inline bool judge(int i, int j, int k) { int cur; for (int t = 1; t <= 4 && i - t >= 0; ++t) { cur = j % powtn[5 - t] / powtn[4 - t]; if (perct[op[i - t]][cur].i == perct[op[i]][k].i) return false; } return true; } int main() { #ifdef fre freopen("in.in", "r", stdin); freopen("out.txt", "w", stdout); #endif powtn[0] = 1; for (int i = 1; i < 5; ++i) powtn[i] = powtn[i - 1] * 10; int t, n, m, g, lst[2], nlst[2], ans; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &g); g += 10; ans = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { perct[i][j].i = j; scanf("%d", &perct[i][j].p); } sort(perct[i] + 1, perct[i] + n + 1); } memset(dp, -1, sizeof(dp)); dp[0][0] = 0; lst[0] = lst[1] = 0; for (int i = 0; i < g; ++i) { nlst[0] = maxn, nlst[1] = 0; scanf("%d", &op[i]); if (op[i] == 0) { for (int j = lst[0]; j <= lst[1]; ++j) { if (~dp[i][j]) { dp[i + 1][j / 10] = max(dp[i + 1][j / 10], dp[i][j]); nlst[0] = min(nlst[0], j / 10); nlst[1] = max(nlst[1], j / 10); } } } else { for (int j = lst[0]; j <= lst[1]; ++j) { if (~dp[i][j]) { int nj; for (int k = 1; k <= min(n, 9); ++k) { nj = j / 10; if (judge(i, j, k)) { nj += k * powtn[3]; dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + perct[op[i]][k].p); nlst[0] = min(nlst[0], nj); nlst[1] = max(nlst[1], nj); } } } } } memcpy(lst, nlst, sizeof(lst)); } for (int i = lst[0]; i <= lst[1]; ++i) ans = max(ans, dp[g][i]); printf("%.2lf", double(ans) / 100); } }
事实上假若我的代码没有写错的话，选择前9的版本理论上应该是兼容前5的版本的。但我的代码在OJ上判的是WA。可能也从另一方面佐证了我的质疑。
Pitcher Rotation UVA - 1379 之疑
原文：https://www.cnblogs.com/jionkitten/p/12984866.html