怎么用动态规划啊？请大侠帮帮忙 [复制链接]

某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
　　为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
　　现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
　　请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入格式 Input Format
  　　第一行是两个数字n(0<n<50，表示路灯的总数)和c(1<＝c<=n老张所处位置的路灯号)；
　　接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。

输出格式 Output Format
  　　一个数据，即最少的功耗(单位：J，1J＝1W·s)。
输入样例

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

输出样例
270

貌似这道题是回溯法

type arr=array[1..100] of 0..1;
var d,w:array[1..100] of integer;
    n,c,i,t:longint;
    min:longint;
    bb:arr;
    input,output:text;

procedure search(bp,t,wt,fx:integer;bb:arr);
var i,j,tl,tr:longint;
    wl,wr:longint;
    b:arr;
begin
  for i:=1 to n do b:=bb;
  if fx=1 then
    begin
    i:=bp+1; wr:=wt; tr:=t+d-d[i-1];
    while b=0 do
      begin
      i:=i+1; tr:=tr+d-d[i-1]
      end;
      wr:=wr+tr*w; b:=0;
      if wr>=min then exit
                else
                  if (i<n) then
                    begin
                    search(i,tr,wr,1,b);
                    search(i,tr,wr,-1,b);
                    end
                    else
                    begin
                      j:=n;
                      while (j>1) and (wr<min) do
                      begin
                        j:=j-1;
                        tr:=tr+(d[j+1]-d[j]);
                        wr:=wr+b[j]*tr*w[j];
                      end;
                      if (j=1) and (wr<min) then min:=wr;
                    end;
    end
    else
      begin
      i:=bp-1;wl:=wt;tl:=t+d[i+1]-d;
      while b=0 do
        begin
        i:=i-1; tl:=tl+d[i+1]-d;
        end;
      wl:=wl+tl*w;b:=0;
      if wl>=min then exit
        else
          if i>1 then
              begin
              search(i,tl,wl,1,b);
              search(i,tl,wl,-1,b);
              end
          else
            begin
              j:=1;
              while (j<n) and (wl<min) do
                begin
                j:=j+1;
                tl:=tl+(d[j]-d[j-1]);
                wl:=wl+b[j]*tl*w[j];
                end;
              if (j=n) and (wl<min) then min:=wl;
              end;
      end;
end;

begin {main}
assign(input,'power.in');reset(input);
readln(input,n,c);
for i:=1 to n do readln(input,d,w);
close(input);
for i:=c-1 downto 1 do
begin
  t:=t+d[i+1]-d;
  min:=min+t*w;
end;
t:=2*t;
for i:=c+1 to n do begin t:=t+d-d[i-1];min:=min+t*w;end;
for i:=1 to n do bb:=1;
bb[c]:=0;
search(c,0,0,1,bb); search(c,0,0,-1,bb);
assign(output,'power.out'); rewrite(output);
writeln(output,min); close(output)
end.

  帖子地址： http://tsc13579.spaces.live.com/Blog/cns%21C875510BCE30B997%21330.entry  收藏到我的口袋  复制给好友 举报
  你查询的问题是：关 路灯  动态规划 
题目大意：

Dobrica得到一份有趣的工作。每天早上他要将村庄里所有的路灯关闭，路灯都是安排在一条道路的一侧的。

Dobrica每天5点开始工作。一开始，他站在某个路灯的旁边。每个路灯有一个功率，也就是每秒钟消耗的能量数。由于Dobrica是个很有经济头脑的人，他希望所有路灯消耗的总能量最少。

Dobrica的速度是每秒钟一米。关闭路灯不需要时间，因为它可以在路过的时候随手关掉。

请你写一个程序，帮助Dobrica安排一个关灯的路线，使得所有路灯所消耗的总的能量最少。


解题思路：

很经典的一道动态规划的题目。

考虑到对于任意一个时刻，关闭的路灯肯定是连续的（古人云，人已至此，不关白不关）。我们这样定义状态：

R[i,j,1] —— 第i号到第j号路灯被关闭，且Dobrica在第i号路灯的情况下，消耗的最少能量。

R[i,j,2] —— 第i号到第j号路灯被关闭，且Dobrica在第j号路灯的情况下，消耗的最少能量。

有以下转移方程式：

R[i,j,1] = Min{ R[i+1,j,1] + (W[1..i]+W[j+1..N])*(D[i+1]-D) , R[i+1,j,2] + (W[1..i]+W[j+1..N])*(D[j]-D) }

R[i,j,2] = Min{ R[i,j-1,1] + (W[1..i-1]+W[j..N])*(D[j]-D[j-1]) , R[i,j-1,2] + (W[1..i-1]+W[j..N])*(D[j]-D) }

整个算法的时间复杂度是O(N2)。


启示：连续性是人走路的特征，分析出了这个特征就要用，要么就是基于联通性的DP，要么就是记录某一段已经被走过，左右两边加两个朝外连接的插头，有点类似联通性DP，以前的一道USACO月赛题也是类似的思路才好做，这种走动问题可以用类似的方法来想。




{
  Izborne pripreme 2001 - Prvi izborni ispit
  Zadatak STRUJA
  Autor rjesenja Mladen Kolar
  Nesluzbeno rjesenje
}

var
    udalj,trosi:array[1..1000] of longint;
    n,gdje:integer;
    lijevo,desno,potrosnja:array[1..1000,1..1000] of longint;

procedure readinp;
var
    f:text;
    i:integer;
begin
    assign(f,'POWER.in');
    reset(f);
    readln(f,n);
    readln(f,gdje);
    for i:=1 to n do readln(f,udalj,trosi);
    close(f);
end;

procedure solve;
var
    i,j:integer;
    x:longint;

    function min(a,b:longint):longint;
    begin
        if a>b then min:=b else min:=a;
    end;



begin

    x:=0;
    for i:=1 to n do x:=x+trosi;
    for i:=1 to n do
        begin
            potrosnja[i,i]:=x-trosi;
            for j:=1+i to n do potrosnja[i,j]:=potrosnja[i,j-1]-trosi[j];
        end;

    lijevo[1,n]:=maxlongint; desno[1,n]:=maxlongint;
    lijevo[gdje,gdje]:=0; desno[gdje,gdje]:=0;

    for i:=gdje+1 to n do
      begin
        desno[gdje,i]:=desno[gdje,i-1]+(udalj-udalj[i-1])*potrosnja[gdje,i-1];
        lijevo[gdje,i]:=desno[gdje,i]+(udalj-udalj[gdje])*potrosnja[gdje,i];
      end;

    for i:=gdje-1 downto 1 do
      begin
        lijevo[i,gdje]:=lijevo[i+1,gdje]+(udalj[i+1]-udalj)*potrosnja[i+1,gdje];
        desno[i,gdje]:=lijevo[i,gdje]+(udalj[gdje]-udalj)*potrosnja[i,gdje];
      end;

    for i:=gdje-1 downto 1 do
        for j:=gdje+1 to n do
            begin
                lijevo[i,j]:=min(lijevo[i+1,j]+(udalj[i+1]-udalj)*potrosnja[i+1,j],
                                desno[i+1,j]+(udalj[j]-udalj)*potrosnja[i+1,j]);
                desno[i,j]:=min(desno[i,j-1]+(udalj[j]-udalj[j-1])*potrosnja[i,j-1],
                                lijevo[i,j-1]+(udalj[j]-udalj)*potrosnja[i,j-1]);
            end;

end;

procedure writesol;
var
    f:text;
begin
    assign(f,'POWER.out');
    rewrite(f);
    if lijevo[1,n]<desno[1,n] then
        writeln(f,lijevo[1,n])
    else
        writeln(f,desno[1,n]);
    close(f);
end;

begin
    readinp;
    solve;
    writesol;
end.