P1220 關路燈

題目描述

某一村莊在一條路線上安裝了n盞路燈，每盞燈的功率有大有小（即同一段時間內消耗的電量有多有少）。老張就住在這條路中間某一路燈旁，他有一項工作就是每天早上天亮時一盞一盞地關掉這些路燈。

為了給村裡節省電費，老張記錄下了每盞路燈的位置和功率，他每次關燈時也都是儘快地去關，但是老張不知道怎樣去關燈才能夠最節省電。他每天都是在天亮時首先關掉自己所處位置的路燈，然後可以向左也可以向右去關燈。開始他以為先算一下左邊路燈的總功率再算一下右邊路燈的總功率，然後選擇先關掉功率大的一邊，再回過頭來關掉另一邊的路燈，而事實並非如此，因為在關的過程中適當地調頭有可能會更省一些。

現在已知老張走的速度為1m/s，每個路燈的位置（是一個整數，即距路線起點的距離，單位：m）、功率（W），老張關燈所用的時間很短而可以忽略不計。

請你為老張編一程式來安排關燈的順序，使從老張開始關燈時刻算起所有燈消耗電最少（燈關掉後便不再消耗電了）。

輸入輸出格式

文件第一行是兩個數字n(0<n<50，表示路燈的總數)和c(1<＝c<=n老張所處位置的路燈號)；

接下來n行，每行兩個數據，表示第1盞到第n盞路燈的位置和功率。

一個數據，即最少的功耗(單位：J，1J＝1W·s)。

輸入輸出樣例

5 3
2 10
3 20
5 20
6 30
8 10

270  

說明

輸出解釋：

{此時關燈順序為3 4 2 1 5，不必輸出這個關燈順序}

這道題採用動態規劃的思想，用f[i][j][0]表示關了[I,j]這個區間的燈，最後關的是第i盞；f[i][j][1]表示關了[I,j]這個區間的燈，最後關的是第j盞。Mon[i]表示從1到i的燈的費用。未wz[i]表示第i盞燈的位置。動歸式如下：

f[i][j][0]=min(f[i+1][j][0]+(mon[n]-(mon[j]-mon[i]))*(wz[i+1]-wz[i]),f[i+1][j][1]+(mon[n]-(mon[j]-mon[i]))*(wz[j]-wz[i]));

f[i][j][1]=min(f[i][j-1][0]+(mon[n]-(mon[j-1]-mon[i-1]))*(wz[j]-wz[i]),f[i][j-1][1]+(mon[n]-(mon[j-1]-mon[i-1]))*(wz[j]-wz[j-1]));

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1001;
 7 int n,where;
 8 int pos[MAXN];
 9 int mon[MAXN];
10 int dp[MAXN][MAXN][3];
11 int main()
12 {
13     freopen("power.in","r",stdin);
14     freopen("power.out","w",stdout);
15     cin>>n>>where;
16     for(int i=1;i<=n;i++)
17     {
18         cin>>pos[i]>>mon[i];        
19         mon[i]+=mon[i-1];    
20     }
21     memset(dp,0x7f,sizeof(dp));
22     dp[where][where][0]=dp[where][where][1]=0;
23     for(int j=where;j<=n;++j)// 每一盞路燈的後半部分 
24     {
25         for(int i=j-1;i>=1;--i)// 前半部分 
26         {
27             // 最後關的是i 
28             dp[i][j][0]=min(dp[i+1][j][0]+(mon[n]-(mon[j]-mon[i]))*(pos[i+1]-pos[i]),
29                             dp[i+1][j][1]+(mon[n]-(mon[j]-mon[i]))*(pos[j]-pos[i]));
30             // 最後關的是j 
31             dp[i][j][1]=min(dp[i][j-1][0]+(mon[n]-(mon[j-1]-mon[i-1]))*(pos[j]-pos[i]),
32                             dp[i][j-1][1]+(mon[n]-(mon[j-1]-mon[i-1]))*(pos[j]-pos[j-1]));
33         }
34     }
35     cout<<min(dp[1][n][0],dp[1][n][1]);
36     return 0;
37 }