P1220 关路灯

[f[i][j]表示i到j的灯已经灭了 ]

但是要转移到其它状态就很困难，所以我们加一维度表示为当前走到左端点还是右端点，然后分类讨论，一种是沿着当前的方向继续走，一种是改变方向回去

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i(j);i<=k;++i)
#define drp(i,j,k) for(int i(j);i>=k;--i)
#define repg(x) for(int i(G.head[x]);i;i=G.next[i])
#define bug cout<<"~~~~~~~~~~~~~"<<'
';
using std::cin;
using std::cout;
typedef long long lxl;
template<typename T>
inline T  max( T a, T b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min( T a, T b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x, char cc) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar(cc);
}
const int N = 57;

int c;
int p[N], w[N];
int f[N][N][2];
int n;
inline int calc(int x, int y, int l, int r) {
	return (p[y] - p[x]) * (w[n] - (w[r] - w[l - 1]) );
}//l~r的灯已经关闭了

int main() {
	read(n);
	read(c);
	rep(i, 1, n) {
		read(p[i]);
		read(w[i]);
		w[i] = w[i - 1] + w[i];
	}

	memset(f, 0x3f, sizeof f);

	f[c][c][0] = f[c][c][1] = 0;

	rep(len, 2, n) {
		rep(l, 1, n - len + 1) {
			int r = l + len - 1;
			f[l][r][0] = min(f[l + 1][r][0] + calc(l, l + 1, l + 1, r), f[l + 1][r][1] + calc(l, r, l + 1, r));
			f[l][r][1] = min(f[l][r - 1][1] + calc(r - 1, r, l, r - 1), f[l][r - 1][0] + calc(l, r, l, r - 1));
		}
	}
	out(min(f[1][n][0], f[1][n][1]), '
');
	return 0;
}