【题目描述】：
Czy是个大丧失，非常喜欢bm。他经常挑战bm的极限，同时b很多的mz。(虽然也许质量不容乐观)
这一天，Czy又开始了他的极限挑战。在一个数轴上有n个maze,她们都在等待着Czy的到来。Czy一开始站在k号妹子的旁边，他需要搞定所有的妹子(由于他向fewdan学会了绝技，所以搞定妹子的时间是无限接近于0的，也就是一瞬间就搞定而不用花额外的时间)。妹子们都很没有耐心，每让她们多等1s,她们就会增加w[i]的不开心值。现在，Czy从k号妹子这里出发，以1m/s的速度开始行动，他希望在搞定所有maze的情况下使得她们的不开心值总和最小，于是他找到了即将在NOIP2017 AK的你来帮他解决这个问题。
【输入描述】：
输入文件的第一行包含一个整数N，2<=N<=1000，表示maze的数量。
第二行包含一个整数V，1<=V<=N，表示开始时czy站在几号maze的旁边。
接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每个妹子，其中0<=D<=1000，0<=W<=1000。D表示MM在数轴上的位置(单位: m)，W表示每秒钟会增加的不开心值。（数据按D值有序给出）
【输出描述】：
一个整数，最小的不开心值。(答案不超过10^9)
【样例输入】：
4
3
2 2
5 8
6 1
8 7【样例输出】：
56【样例说明】：
【时间限制、数据范围及描述】：
时间：1s 空间：256M
对于40%的数据，2<=n<=7
对于100%的数据，2<=n<=1000 0<=D<=1000 0<=w<=1000
我日昍晶！时隔一年多，终于又让我遇到了区间DP题，然而我这题比赛时调了一个小时没调出来，回来一看发现忘记把每一个小区间外面的值给带上了......
说实话我觉得秤砣这个标程有点问题......秤砣垃圾！
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1005; 5 int n,m; 6 int f[MAX][MAX][2],pre[MAX]; 7 struct MZ{ 8 int x,y; 9 }mz[MAX]; 10 inline int read(){ 11 int an=0,x=1;char c=getchar(); 12 while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();} 13 while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();} 14 return an*x; 15 } 16 int main(){ 17 freopen ("czybm.in","r",stdin); 18 freopen ("czybm.out","w",stdout); 19 int len,i,j; 20 n=read();m=read();pre[0]=0; 21 for (i=1;i<=n;i++){ 22 mz[i].x=read();mz[i].y=read(); 23 pre[i]=pre[i-1]+mz[i].y; 24 } 25 for (i=1;i<=n;i++) f[i][i][0]=f[i][i][1]=pre[n]*abs(mz[i].x-mz[m].x); 26 for (len=2;len<=n;len++){ 27 for (i=1;i<=n-len+1;i++){ 28 j=i+len-1; 29 f[i][j][0]=min((pre[n]-pre[j]+pre[i])*(mz[i+1].x-mz[i].x)+f[i+1][j][0], 30 (pre[n]-pre[j-1]+pre[i-1])*(mz[j].x-mz[j-1].x)+f[i][j-1][1]+(pre[n]-pre[j]+pre[i-1])*(mz[j].x-mz[i].x)); 31 f[i][j][1]=min((pre[n]-pre[j-1]+pre[i-1])*(mz[j].x-mz[j-1].x)+f[i][j-1][1], 32 (pre[n]-pre[j]+pre[i])*(mz[i+1].x-mz[i].x)+f[i+1][j][0]+(pre[n]-pre[j]+pre[i-1])*(mz[j].x-mz[i].x)); 33 } 34 } 35 printf("%d",min(f[1][n][1],f[1][n][0])); 36 return 0; 37 }