首页 > 代码库 > HDU 2571 命运

HDU 2571 命运

2024-07-14 19:02:29   221人阅读

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

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 LOCAL14         freopen("2571in.txt", "r", stdin);15     #endif16 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\n", dp[row][col]);43     }44     return 0;45 }
代码君

 


联系
我们