P1220 关路灯

思路

\(f_{i,j,0}\)表示关了\(i\~ j\)的灯并且当前在\(i\)(\(f_{i,j,0}\))或\(j\)(\(f_{i,j,1}\))
这里的\(f_{i,j,0}\)和\(f_{i,j,1}\)可以由\(f_{i + 1,j,0},f_{i + 1,j,1},f_{i,j - 1,0},f_{i,j - 1,1}\)转移过来。
代价就是除了这几盏灯外其他灯的总功率\(\times\)总时间。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 60;
int n,k;
int idx[N],s[N];
int f[N][N][2];
int main () {
	cin >> n >> k;
	for (int i = 1;i <= n;i++) {
		cin >> idx[i] >> s[i];
		s[i] += s[i - 1];
	}
	memset (f,0x3f,sizeof (f));
	f[k][k][0] = f[k][k][1] = 0;
	for (int len = 2;len <= n;len++) {
		for (int i = 1;i + len - 1 <= n;i++) {
			int j = i + len - 1;
			f[i][j][0] = min (f[i + 1][j][0] + (idx[i + 1] - idx[i]) * (s[n] - (s[j] - s[i])),
			f[i + 1][j][1] + (idx[j] - idx[i]) * (s[n] - (s[j] - s[i])));
			f[i][j][1] = min (f[i][j - 1][0] + (idx[j] - idx[i]) * (s[n] - (s[j - 1] - s[i - 1])),
			f[i][j - 1][1] + (idx[j] - idx[j - 1]) * (s[n] - (s[j - 1] - s[i - 1])));
		}
	}
	cout << min (f[1][n][0],f[1][n][1]) << endl;
	return 0;
}