1336 - Fixing the Great Wall（DP）
本題極為經典，是動態規劃中“未來費用”的計算， 因為起點固定且維修時間忽略，所以任意時間已經修復的點一定是一個連續的區間 。因此我們用d[i][j][k]表示已經修理完區間[i,j]
且現在正在點k ，如果k為0，在i點，如果k為1，在j點。這顯然已經可以表示所有狀態，那麼怎麼維護時間這個量呢？ 我們可以發現，每過t時間，沒有維修的點都將增加費用，所以我們不妨先預處理求出每個區間的d值只和，然後將沒有維修過的點乘以時間就好了，這樣，我們就可以動態維護費用 。另外，最後的答案一定包括所有點的c值只和 。
另外需要注意雖然題目說答案不超過1000000000，但是中間值有可能超int ，所以我們不妨都用double 。
然而我用cout<
細節參見代碼：
#include
using namespace std;
const double INF = 30000000000;
int n,kase = 0,vis[1005][1005][5];
double v,x,d[1005][1005][5],sum[1005];
struct point{
double x,c,d;
bool operator < (const point& v) const {
return x < v.x;
}
}a[1005];
double dp(int i,int j,int k) {
if(i==1&&j==n) return 0;
double& ans = d[i][j][k];
if(vis[i][j][k] == kase) return ans;
vis[i][j][k] = kase;
ans = INF;
double p = (k == 0 ? a[i].x : a[j].x);
if(i>1) {
double t = abs(a[i-1].x - p)/v;
double u = (sum[i-1]+sum[n]-sum[j])*t+a[i-1].c;
ans = min(ans,dp(i-1,j,0)+u);
}
if(j>n>>v>>x) {
if(!n&&!v&&!x) return 0;
for(int i=1;i<=n;i++) scanf(%lf%lf%lf,&a[i].x,&a[i].c,&a[i].d);
sort(a+1,a+n+1);
++kase;
sum[0] = 0;
for(int i=1;i<=n;i++) {
sum[i] = sum[i-1] + a[i].d;
}
a[0].x = -INF; a[n+1].x = INF;
double ans = INF;
for(int i=1;i<=n+1;i++) {
if(a[i-1].x
