关于一类动态规划题的总结

关于一类DP题目的总结

1

题面：N个数字(有正有负)排成一环，选出不重叠的连续的K段使得和最大N <= 100000, K <= 10

如3方法断环成链

F[i][j]表示前i个数取了j段的最大和

F[i][j] = Max{ F[k][j-1]+ S[i] - S[k] }, F[i-1][j] , k<i

= Max{Max{ F[k][j-1] - S[k] } + S[i], F[i-1][j] }, k<i

优化：G[i][j]=Max{ F[k][j-1] - S[k] }, k<i

时间复杂度O(N2)

从学长资料里蒯了一些

也加上了最近KS的两道题

希望能对读者有所帮助

也属于未完待续类型吧