Luogu 1220

题目分析：

• $定义f\left[i\right]\left[j\right]\left[0\right]表示关掉区间[i,j]的灯，最后停在i的最小耗电量，f\left[i\right]\left[j\right]\left[1\right]表示停在j$定义f[i][j][0]表示关掉区间[i,j]的灯，最后停在i的最小耗电量，f[i][j][1]表示停在j
• 边界： $f\left[c\right]\left[c\right]\left[0\right]=f\left[c\right]\left[c\right]\left[1\right]=0,f\left[i\right]\left[j\right]\left[0/1\right]=INF$f[c][c][0]=f[c][c][1]=0,f[i][j][0/1]=INF
• 转移方程：
  $f\left[i\right]\left[j\right]\left[0\right]=min\left(f\right[i+1\left]\right[j\left]\right[0]+d(i+1,i)\ast P,f[i+1\left]\right[j\left]\right[1]+d(j,i)\ast P)$f[i][j][0]=min(f[i+1][j][0]+d(i+1,i)∗P,f[i+1][j][1]+d(j,i)∗P)
  $f\left[i\right]\left[j\right]\left[1\right]=min\left(f\right[i\left]\right[j-1\left]\right[1]+d(j-1,j)\ast P,f[i\left]\right[j-1\left]\right[0]+d(i,j)\ast P)$f[i][j][1]=min(f[i][j−1][1]+d(j−1,j)∗P,f[i][j−1][0]+d(i,j)∗P)

Code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 60

int n,f[maxn][maxn][3],c,a[maxn],b[maxn],s[maxn];

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

void readda_() {
	n=read_();c=read_();
	s[0]=0;
	for(int i=1;i<=n;++i) {
		a[i]=read_();
		b[i]=read_();
		s[i]=s[i-1]+b[i];
	}
	memset(f,0x7f,sizeof(f));
	f[c][c][0]=f[c][c][1]=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]+(a[i+1]-a[i])*(s[i]+s[n]-s[j]),f[i+1][j][1]+(a[j]-a[i])*(s[i]+s[n]-s[j]));
			f[i][j][1]=min(f[i][j-1][1]+(a[j]-a[j-1])*(s[i-1]+s[n]-s[j-1]),f[i][j-1][0]+(a[j]-a[i])*(s[i-1]+s[n]-s[j-1]));
		}
	}
	printf("%d",min(f[1][n][0],f[1][n][1]));
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}