codeforces765-div2 C(dp一生之敌)

题目 题意: 在大小为0-m的一维数轴上，给定n个柱子xi，每个点均有其限速ai.即在x[i]到x[i+1]一段速度为ai.现在可以删除至多 k个柱子，求从0到m的最短时间。(0处必有柱子，且不能删除) 思路: n = 500.猜测是一个n^3的算法，dp. dp[i][j]表示前i个柱子，删除j个，且不删除第i个的最小花费. dp2[i][j]表示前i个柱子，删除j个，且删除第i个的最小花费. 此处的最小花费是前从0到i+1的最小花费，不然不好写，绕了半天才看懂.

dp2[i][j] = min(dp2[i-1][j-1],dp[i-1][j-1]) + a[i] * (x[i+1] - x[i]) dp[i][j] = min(dp[i][j],dp2[t][i-t] + a[t] * (a[x+1]-x[i-t+1]) *), 1 >m>>k; for(int i=1;i>x[i]; for(int i=1;i>a[i]; x[n+1] = m; if(n == 1) { ans = (m - x[1]) * a[1]; cout