HDU 2571 命运——DP

注意把边界赋值为-INF；

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1010;int n, m, a[25][maxn], dp[25][maxn];int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } for (int i = 1; i <= n; i++) { dp[i][0] = -INF; } for (int i = 1; i <= m; i++) { dp[0][i] = -INF; } dp[1][0] = dp[0][1] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); for (int k = 2; k <= j; k++) { if (j % k == 0) { dp[i][j] = max(dp[i][j], dp[i][j / k]); } } dp[i][j] += a[i][j]; } } printf("%d\n", dp[n][m]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。