問題#
ある村で、$n$ 台の街灯がある道路に設置されています。それぞれの街灯の消費電力は異なります（つまり、同じ時間内に消費される電力量が異なります）。老張はその道路の真ん中にある街灯のそばに住んでおり、毎朝明るくなると、1 台ずつ街灯を消す仕事をしています。
村の電気代を節約するために、老張は各街灯の位置と消費電力を記録しました。彼は街灯を消すとき、できるだけ早く消そうとしますが、どのように消すのが最も電気を節約できるのかは分かりません。彼は毎朝明るくなると、まず自分の位置にある街灯を消し、その後、左または右に移動して街灯を消します。最初は、左側の街灯の総消費電力を計算し、次に右側の街灯の総消費電力を計算し、消費電力が大きい方を先に消してから、もう一方の街灯を消すことを考えていましたが、実際には、消す過程で適切に方向転換することで、より節約できる可能性があります。
老張の移動速度は $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;
}