DP的优化
计划安排
https://ac.nowcoder.com/acm/contest/30466/I
O（n^3）思路： 先求出t和c的前缀和sumt, sumc dp[i][j]表示前i个任务分成j批的最小代价，这样我们算的可以知道这是第几批，同时枚举第j批和第j-1批的分界点找到最小代价的。状态转移方程： dp[i][j] = min{dp[k][j-1] + (sj+sumt[i])(sumc[i]-sum[k])}; 0 <= k < i 前k个任务分了j-1批，k+1 ~ i分成了一批。 时间复杂度较高。 O（n^2）思路： 还是先求前缀和 dp[i]表示前i个任务分成若干批的最小代价，与前一种方法相比，我们不关心这是第几批，在每次分批的时候把对后面所有任务造成的影响加上即可，影响为s*(sumc[n]-sum[j]) j为分割点。状态转移方程： dp[i] = min{dp[j] + sumt[i](sumc[i]-sumc[j]) + s(sumc[n]-sumc[j])} 0 <= j < i;
投递美团等公司10个岗位 >
