題目#
某一村莊在一條路線上安裝了 $n$ 盞路燈，每盞燈的功率有大有小（即同一段時間內消耗的電量有多有少）。老張就住在這條路中間某一路燈旁，他有一項工作就是每天早上天亮時一盞一盞地關掉這些路燈。
為了給村裡節省電費，老張記錄下了每盞路燈的位置和功率，他每次關燈時也都是盡快地去關，但是老張不知道怎樣去關燈才能夠最節省電。他每天都是在天亮時首先關掉自己所處位置的路燈，然後可以向左也可以向右去關燈。開始他以為先算一下左邊路燈的總功率再算一下右邊路燈的總功率，然後選擇先關掉功率大的一邊，再回過頭來關掉另一邊的路燈，而事實並非如此，因為在關的過程中適當地調頭有可能會更省一些。
現在已知老張走的速度為 $1m/s$，每個路燈的位置（是一個整數，即距路線起點的距離，單位：$m$）、功率（$W$），老張關燈所用的時間很短而可以忽略不計。
請你為老張編一程序來安排關燈的順序，使從老張開始關燈時刻算起所有燈消耗電最少（燈關掉後便不再消耗電了）。
$1\le n\le50$，$1\le c\le n$。
題解#
這個題不太好想到動態規劃。
然後根據貪心，在從點 i 去關點 j 的路燈時，所有經過的路燈都會隨手關掉（不耗時間），所以我們可以確定，若 i 點和 j 點的路燈已經關閉，那麼區間 i...j 的路燈已經全部關閉，而且關完後，最優策略一定是在點 i 處或者點 j 處。
yinyuqin 大佬的話
所以我們設f[i][j][0/1]表示關完區間 i 到 j 的燈並且最後在 i/j
注意轉移的時候第 i/j 盞燈還沒滅，要消耗電量
問題#
初始化！！！
代碼#
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
struct U
{
int pos, P;
}u[N];
int n, c;
int sum[N];
int f[N][N][2];//表示目前已經關了完了i——j盞燈，最後一盞關的是i/j的路徑組成的集合 屬性：最小電量
int main()
{
memset(f, 0x3f, sizeof f);
n = read(), c = read();
for(int i = 1;i <= n;i++)
{
u[i].pos = read(), u[i].P = read();
sum[i] = sum[i - 1] + u[i].P;
}
f[c][c][1] = f[c][c][0] = 0;
for(int L = 2; L <= n;L++)
{
for(int i = 1;i + L - 1 <= n;i++)
{
int j = i + L - 1;
f[i][j][0] = min(f[i + 1][j][0] + (u[i + 1].pos - u[i].pos) * (sum[i]+sum[n]-sum[j]), f[i + 1][j][1] + (u[j].pos - u[i].pos) * (sum[i]+sum[n]-sum[j]));
f[i][j][1] = min(f[i][j - 1][0] + (u[j].pos - u[i].pos) * (sum[i-1]+sum[n]-sum[j-1]), f[i][j - 1][1] + (u[j].pos - u[j - 1].pos) * (sum[i-1]+sum[n]-sum[j-1]));
}
}
cout << min(f[1][n][0], f[1][n][1]);
return 0;
}