关于一类动态规划题的总结
关于一类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的两道题
希望能对读者有所帮助
也属于未完待续类型吧
