HDU 1204 基础DP 非连续字段的最大和

时间:2021-11-26 10:11:17

其实这个感觉是一眼题,只不过我真心太菜了。

题目已经告诉你了,有m段,n个数字,那么我们就只需要dp[m][n]即可,然后最后的答案肯定是dp[m][]的那一行,所以其他行都是没有用的,因为我们可以把dp[m][n]变成dp[2][n]即可。

然后转移方程式dp[i][j] = max(dp[i][j - 1], max(dp[i-1][k])) + a[j];其中i-1<k<j

前面这个表示分成i份,其中最大的一份加上dp[j]

后面这个表示在分成i-1份的时候,然后得出k位中最大的,然后再让a[j]单独成为一份。

记住dp[][i]的时候是只有dp[前一位][i-1]+a[i]的