HDU 2571 命运

感觉是数塔的变形或者是升级版

WA了好几次，和别人代码对拍才发现问题所在

for(k = 2; k <= j; ++k)
    if(j % k == 0)
        dp[i][j] = max(dp[i][j], dp[i][j/k]);

这句代码中，一开始老想着(x,y*k) 其中k>1的事情

然后脑袋一抽筋丢掉了等号，误写成了k < j

事实上，k == j的时候是y == 1的情况

还好测试数据严谨。不过当你等着几十行代码手足无措的时候，最后发现某一处落了一个等号，是何等哭笑不得的一件事。

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int INF = -105;
 9 int a[22][1005], dp[22][1005];
10 
11 int main(void)
12 {
13     #ifdef LOCAL
14         freopen("2571in.txt", "r", stdin);
15     #endif
16 
17     int T;
18     scanf("%d", &T);
19     while(T--)
20     {
21         int row, col;
22         scanf("%d%d", &row, &col);
23         int i, j, k;
24         for(i = 1; i <= row; ++i)
25             for(j = 1; j <= col; ++j)
26                 scanf("%d", &a[i][j]);
27         for(i = 0; i <= row; ++i)
28             dp[i][0] = INF;
29         for(i = 0; i <= col; ++i)
30             dp[0][i] = INF;
31         dp[0][1] = dp[1][0] = 0;
32         for(i = 1; i <= row; ++i)
33             for(j = 1; j <= col; ++j)
34             {
35                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
36                 for(k = 2; k <= j; ++k)
37                     if(j % k == 0)
38                         dp[i][j] = max(dp[i][j], dp[i][j/k]);
39                 dp[i][j] += a[i][j];
40             }
41 
42         printf("%d
", dp[row][col]);
43     }
44     return 0;
45 }

代码君