?題目描述?Description

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

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

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

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

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

輸入描述?Input Description

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

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

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

輸出描述?Output Description

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

樣例輸入?Sample Input

4

3

2?2

5?8

6?1

8?7

樣例輸出?Sample Output

56

思路

對于小數(shù)據(jù)來說，爆搜可以過，n<=50，然而對于大的數(shù)據(jù)，當(dāng)n<=1000時，只能過7個點。

設(shè)f[i,j,k](k=1或2)表示已經(jīng)關(guān)過的MM區(qū)間為[i,j]，k=1表示當(dāng)前在左端點i位置，k=2表示當(dāng)前在右端點j位置。

f[i,j,0]=min{ f[i+1,j,1] + (w[i] + (w[n] - w[j]))*(d[i+1] - d[i]),f[i+1,j,2] + (w[i]+ (w[n] - w[j]))*(d[i+1] - d[i]) }f[i,j,2]=min{ f[i,j-1,1] + (w[i-1] + (w[n] - w[j-1]))*(d[j] - d[i]),f[i,j-1,2] + (w[i-1] + (w[n] - w[j-1]))*(d[j] - d[j-1]) }初始狀態(tài)：f[s,s,1]=s[s,s,2]=0目標(biāo)狀態(tài)：min{ f[1,n,1] , f[1,n,2] }時間復(fù)雜度：O(n^2)DFS varn,c,ans,total:longint;dis,w:array[0..60]of longint;f:array[0..60]of boolean;procedure init; beginassign(input,'power.in');assign(output,'power.out');reset(input);rewrite(output); end;procedure terminate; beginclose(input); close(output);halt; end;procedure dfs(t,tot,total,t1:longint); vari:longint; beginfor i:=t-1 downto 1 doif f[i] thenbeginif tot+(dis[t]-dis[i])*(total-w[t])<ans thenbeginf[i]:=false;dfs(i,tot+(dis[t]-dis[i])*(total-w[t]),total-w[t],t1+1);f[i]:=true;break;end;end;for i:=t+1 to n doif f[i] thenbeginif tot+(dis[i]-dis[t])*(total-w[t])<ans thenbeginf[i]:=false;dfs(i,tot+(dis[i]-dis[t])*(total-w[t]),total-w[t],t1+1);f[i]:=true;break;end;end;if t1=n thenif tot<ans thenbeginans:=tot;exit;end; end;procedure main; vari:longint; beginreadln(n,c);total:=0;for i:=1 to n dobeginreadln(dis[i],w[i]);f[i]:=true;total:=total+w[i];end;ans:=maxlongint;f[c]:=false;dfs(c,0,total,1);writeln(ans); end;begininit;main;terminate; end. View Code

?

DP

program CloseTheLight; uses math; var n,c,i,p,j,k,v1,a:longint;v,s:array[0..1000] of longint;f:array[0..1000,0..1000,0..1] of longint; beginread(n,c);for i:=1 to n dobeginread(v[i],a);s[i]:=s[i-1]+a;end;filldword(f,sizeof(f) div 4,maxlongint);f[c,c,1]:=0;f[c,c,0]:=0;for p:=0 to n-1 dofor i:=1 to n-p dobeginj:=i+p;for k:=0 to 1 dobeginif k=0 then v1:=i else v1:=j;if f[i,j,k]<maxlongint thenbeginif i>0 then f[i-1,j,0]:=min(f[i-1,j,0],f[i,j,k]+(s[i-1]+s[n]-s[j])*(v[v1]-v[i-1]));if j<n then f[i,j+1,1]:=min(f[i,j+1,1],f[i,j,k]+(s[i-1]+s[n]-s[j])*(v[j+1]-v[v1]));end;end;end;writeln(min(f[1,n,0],f[1,n,1])); end. View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/yangqingli/p/4792874.html

總結(jié)

以上是生活随笔為你收集整理的[CODEVS1258]关路灯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。