【描述】
多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關(guān)掉他所在村莊的街燈。所有的街燈都被設(shè)置在一條直路的同一側(cè)。
多瑞卡每天到早晨5點(diǎn)鐘都按時(shí)起床，然后他開始關(guān)燈。開始時(shí)，他站在某一盞路燈的旁邊。
每盞燈都有一個(gè)給定功率的電燈泡，因?yàn)槎喽丝ㄓ兄杂X的節(jié)能意識(shí)，他希望在耗電能總數(shù)最少的情況下將所有的燈關(guān)掉。
多端卡因?yàn)樘哿耍灾荒芤?m/s的速度行走。關(guān)燈不需要花費(fèi)額外的時(shí)間，因?yàn)楫?dāng)他通過時(shí)就能將燈關(guān)掉。
編寫程序，計(jì)算在給定路燈設(shè)置，燈泡功率以及多端卡的起始位置的情況下關(guān)掉所有的燈需耗費(fèi)的最小能量。
【輸入】
輸入文件的第一行包含一個(gè)整數(shù)N，2≤N≤1000，表示該村莊路燈的數(shù)量。
第二行包含一個(gè)整數(shù)V，1≤V≤N，表示多瑞卡開始關(guān)燈的路燈號(hào)碼。
接下來的N行中，每行包含兩個(gè)用空格隔開的整數(shù)D和W，用來描述每盞燈的參數(shù)，其中0≤D≤1000，0≤W≤1000。D表示該路燈與村莊開始處的距離(用米為單位來表示)，W表示燈泡的功率，即在每秒鐘該燈泡所消耗的能量數(shù)。路燈是按順序給定的。
【輸出】
輸出文件的第一行即唯一的一行應(yīng)包含一個(gè)整數(shù)，即消耗能量之和的最小值。注意結(jié)果不超過1,000,000,000。
【樣例】
| POWER.IN | POWER.OUT |
4
3
2 2
5 8
6 1
8 7 | 56 |
【分析】
用c[i][j]表示關(guān)掉i到j(luò)的燈，剩下的燈的功率。
f[i][j][0]表示v左面關(guān)掉i，右面關(guān)掉j盞燈，最后停到左面。
f[i][j][1]表示v左面關(guān)掉i，右面關(guān)掉j盞燈，最后停到右面。
初始條件：
f[0,0,0]=f[1,0,0]=0
轉(zhuǎn)移方程：//對(duì)于所有的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]}
最終結(jié)果： 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: