1258 關路燈

?

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 大師 Master 題目描述?Description

多瑞卡得到了一份有趣而高薪的工作。每天早晨他必須關掉他所在村莊的街燈。所有的街燈都被設置在一條直路的同一側。

多瑞卡每晚到早晨5點鐘都在晚會上，然后他開始關燈。開始時，他站在某一盞路燈的旁邊。

每盞燈都有一個給定功率的電燈泡，因為多端卡有著自覺的節能意識，他希望在耗能總數最少的情況下將所有的燈關掉。

多端卡因為太累了，所以只能以1m/s的速度行走。關燈不需要花費額外的時間，因為當他通過時就能將燈關掉。

編寫程序，計算在給定路燈設置，燈泡功率以及多端卡的起始位置的情況下關掉所有的燈需耗費的最小能量。

輸入描述?Input Description

輸入文件的第一行包含一個整數N，2≤N≤1000，表示該村莊路燈的數量。

第二行包含一個整數V，1≤V≤N，表示多瑞卡開始關燈的路燈號碼。

接下來的N行中，每行包含兩個用空格隔開的整數D和W，用來描述每盞燈的參數，其中0≤D≤1000，0≤W≤1000。D表示該路燈與村莊開始處的距離(用米為單位來表示)，W表示燈泡的功率，即在每秒種該燈泡所消耗的能量數。路燈是按順序給定的。

輸出描述?Output Description

輸出文件的第一行即唯一的一行應包含一個整數，即消耗能量之和的最小值。注意結果小超過1,000,000,000。

樣例輸入?Sample Input

4

3

2?2

5?8

6?1

8?7

樣例輸出?Sample Output

56

?

#include<iostream> 
#include<cstdio>
#include<cstring>
using namespace std;
int d[100],w[100],s,n;
int f[100][100][3];//如果關閉一個區間的燈，最后人一定在這個區間的左邊或右邊，關了左邊或右邊的燈去中間沒必要。
//f[i][j][0]表示關了[i,j]區間的燈最后人在i點的最優值，f[i][j][1]表示關了[i,j]區間的燈最后人在j點的最優值
int main()
{scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d%d",&d[i],&w[i]),w[i]+=w[i-1];memset(f,127/3,sizeof(f));f[s][s][0]=f[s][s][1]=0;for(int i=s;i>=1;i--)for(int j=i+1;j<=n;j++){f[i][j][0]=min(f[i+1][j][0]+(d[i+1]-d[i])*(w[n]-(w[j]-w[i])),f[i][j][0]);f[i][j][0]=min(f[i+1][j][1]+(d[j]-d[i])*(w[n]-(w[j]-w[i])),f[i][j][0]);f[i][j][1]=min(f[i][j-1][1]+(d[j]-d[j-1])*(w[n]-(w[j-1]-w[i-1])),f[i][j][1]);f[i][j][1]=min(f[i][j-1][0]+(d[j]-d[i])*(w[n]-(w[j-1]-w[i-1])),f[i][j][1]);}printf("%d",min(f[1][n][1],f[1][n][0]));
}

心若向陽，無謂悲傷

?

轉載于:https://www.cnblogs.com/L-Memory/p/6357756.html

總結

以上是生活随笔為你收集整理的codevs1258 关路灯（☆区间dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。