關路燈

某一村莊在一條路線上安裝了n盞路燈，每盞燈的功率有大有小（即同一段時間內(nèi)消耗的電量有多有少）。老張就住在這條路中間某一路燈旁，他有一項工作就是每天早上天亮時一盞一盞地關掉這些路燈。為了給村里節(jié)省電費，老張記錄下了每盞路燈的位置和功率，他每次關燈時也都是盡快地去關，但是老張不知道怎樣去關燈才能夠最節(jié)省電。他每天都是在天亮時首先關掉自己所處位置的路燈，然后可以向左也可以向右去關燈。開始他以為先算一下左邊路燈的總功率再算一下右邊路燈的總功率，然后選擇先關掉功率大的一邊，再回過頭來關掉另一邊的路燈，而事實并非如此，因為在關的過程中適當?shù)卣{(diào)頭有可能會更省一些。現(xiàn)在已知老張走的速度為1m/s，每個路燈的位置（是一個整數(shù)，即距路線起點的距離，單位：m）、功率（W），老張關燈所用的時間很短而可以忽略不計。請你為老張編一程序來安排關燈的順序，使從老張開始關燈時刻算起所有燈消耗電最少（燈關掉后便不再消耗電了）。文件第一行是兩個數(shù)字n(1<=n<=50，表示路燈的總數(shù))和c(1<＝c<=n老張所處位置的路燈號)；接下來n行，每行兩個數(shù)據(jù)，表示第1盞到第n盞路燈的位置和功率。數(shù)據(jù)保證路燈位置單調(diào)遞增。

注意到一個事實，被關的燈一定是連續(xù)的區(qū)間。因為老張不會閃現(xiàn)。然后此題的解法就出來了，是區(qū)間動態(tài)規(guī)劃。\(f[i][j][0/1]\)表示從i到j這個區(qū)間的燈被關了，0表示老張在i上，1表示老張在j上（老張如果到中間去，必定是不優(yōu)的，所以可以直接把狀態(tài)剪掉，這或許叫做最優(yōu)性剪枝？（大霧））。然后狀態(tài)轉(zhuǎn)移方程就出來了。

#include <cstdio> #include <algorithm> using namespace std;const int maxn=55, INF=1e9; int n, c, powersum; int pos[maxn], power[maxn], prepower[maxn]; int f[maxn][maxn][2];int main(){scanf("%d%d", &n, &c);for (int i=1; i<=n; ++i){scanf("%d%d", &pos[i], &power[i]);prepower[i]=prepower[i-1]+power[i];}powersum=prepower[n];for (int i=1; i<=n; ++i) f[i][i][0]=f[i][i][1]=INF;f[c][c][0]=f[c][c][1]=0;for (int l=1; l<n; ++l)for (int i=1; i<=n-l; ++i){int j=i+l, p1=powersum-prepower[j]+prepower[i]; //減去p[i+1~j]int p2=powersum-prepower[j-1]+prepower[i-1]; //減去p[i~j-1]f[i][j][0]=min(f[i+1][j][0]+(pos[i+1]-pos[i])*p1,f[i+1][j][1]+(pos[j]-pos[i])*p1);f[i][j][1]=min(f[i][j-1][1]+(pos[j]-pos[j-1])*p2,f[i][j-1][0]+(pos[j]-pos[i])*p2);}printf("%d", min(f[1][n][0], f[1][n][1]));return 0; }

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

總結

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

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