【描述】
多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關掉他所在村莊的街燈。所有的街燈都被設置在一條直路的同一側。
多瑞卡每天到早晨5點鐘都按時起床，然后他開始關燈。開始時，他站在某一盞路燈的旁邊。
每盞燈都有一個給定功率的電燈泡，因為多端卡有著自覺的節能意識，他希望在耗電能總數最少的情況下將所有的燈關掉。
多端卡因為太累了，所以只能以1m/s的速度行走。關燈不需要花費額外的時間，因為當他通過時就能將燈關掉。
編寫程序，計算在給定路燈設置，燈泡功率以及多端卡的起始位置的情況下關掉所有的燈需耗費的最小能量。
【輸入】
輸入文件的第一行包含一個整數N，2≤N≤1000，表示該村莊路燈的數量。
第二行包含一個整數V，1≤V≤N，表示多瑞卡開始關燈的路燈號碼。
接下來的N行中，每行包含兩個用空格隔開的整數D和W，用來描述每盞燈的參數，其中0≤D≤1000，0≤W≤1000。D表示該路燈與村莊開始處的距離(用米為單位來表示)，W表示燈泡的功率，即在每秒鐘該燈泡所消耗的能量數。路燈是按順序給定的。
【輸出】
輸出文件的第一行即唯一的一行應包含一個整數，即消耗能量之和的最小值。注意結果不超過1,000,000,000。
【樣例】
| POWER.IN | POWER.OUT |
4
3
2 2
5 8
6 1
8 7 | 56 |
【分析】
用c[i][j]表示關掉i到j的燈，剩下的燈的功率。
f[i][j][0]表示v左面關掉i，右面關掉j盞燈，最后停到左面。
f[i][j][1]表示v左面關掉i，右面關掉j盞燈，最后停到右面。
初始條件：
f[0,0,0]=f[1,0,0]=0
轉移方程：//對于所有的i和j，滿足0<i<=v-1，0<j<=n-v
f[0,I,0]=f[0,i-1,0]+c[v-i+1,v]*(d[v-i+1]-d[v-i]){從i-1走到i所耗功率}
f[1,I,0]=f[0,I,0]+c[v-I,v]*(d[v]-d[v-i]){ {從i走到v所耗功率}
f[1,0,j]=f[1,0,j-1]+c[v,v+j-1]*(d[v+j]-d[v+j-1])
f[0,0,j]=f[1,0,j]+c[v,v+j]*(d[v+j]-d[v])
f[0,I,j]=min{f[0,i-1,j]+(d[v-i+1]-d[v-i])*c[v-i+1,v+j]，f[1,i-1,j]+(d[v+j]-d[v-i])*c[v-i+1,v+j]}
f[1,I,j]=min{f[1,I,j-1]+(d[v+j]-d[v+j-1])*c[v-I,v+j-1]，f[0][I,j-1]+(d[v+j]-d[v-i])*c[v-I,v+j-1]}
最終結果： Result=min{f[0,v-1,n-v],f[1,v-1,n-v]}
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1010
4: using namespace std;
5:
6: int c[maxn][maxn];
7: int sum[maxn][maxn];
8: int d[maxn],w[maxn];
9: int n,v;
10: int f[maxn][maxn][2];
11:
12: int main()
13: {
14: freopen("power.in","r",stdin);
15: freopen("power.out","w",stdout);
16:
17: scanf("%d%d",&n,&v);
18: for (int i=1;i<=n;++i) scanf("%d%d",&d[i],&w[i]);
19: for (int i=1;i<=n;++i)
20: for (int j=i;j<=n;++j)
21: sum[i][j]=sum[i][j-1]+w[j];
22: for (int i=1;i<=n;++i)
23: for (int j=i;j<=n;++j)
24: c[i][j]=sum[1][n]-sum[i][j];
25: memset(f,63,sizeof(f));
26: f[0][0][0]=f[0][0][1]=0; //0left 1right
27: for (int i=1;i<=v-1;++i)
28: {
29: f[i][0][0]=f[i-1][0][0]+c[v-i+1][v]*(d[v-i+1]-d[v-i]);
30: f[i][0][1]=f[i][0][0]+c[v-i][v]*(d[v]-d[v-i]);
31: }
32: for (int j=1;j<=n-v;++j)
33: {
34: f[0][j][1]=f[0][j-1][1]+c[v][v+j-1]*(d[v+j]-d[v+j-1]);
35: f[0][j][0]=f[0][j][1]+c[v][v+j]*(d[v+j]-d[v]);
36: }
37: for (int i=1;i<=v-1;++i)
38: for (int j=1;j<=n-v;++j)
39: {
40: f[i][j][0]=min(f[i-1][j][0]+c[v-i+1][v+j]*(d[v-i+1]-d[v-i]),f[i-1][j][1]+c[v-i+1][v+j]*(d[v+j]-d[v-i]));
41: f[i][j][1]=min(f[i][j-1][1]+c[v-i][v+j-1]*(d[v+j]-d[v+j-1]),f[i][j-1][0]+c[v-i][v+j-1]*(d[v+j]-d[v-i]));
42: }
43: printf("%d\n",min(f[v-1][n-v][1],f[v-1][n-v][0]));
44: return 0;
45: }
46:
47: