路灯2
一眼区间 \(dp\) ，定义一个三维数组
\(f[i][j][0]\) 表示 \(i \sim j\) 区间中最后关第 \(i\) 盏灯。
\(f[i][j][1]\) 表示 \(i \sim j\) 区间中最后关第 \(j\) 盏灯。
然后可以退出状态转移方程为
int A=f[i+1][j][0]+(p[i+1]-p[i])*(sum[n]-sum[j]+sum[i]);
int B=f[i+1][j][1]+(p[j]-p[i])*(sum[n]-sum[j]+sum[i]);
int C=f[i][j-1][0]+(p[j]-p[i])*(sum[n]-sum[j-1]+sum[i-1]);
int D=f[i][j-1][1]+(p[j]-p[j-1])*(sum[n]-sum[j-1]+sum[i-1]);
f[i][j][0]=min(A,B);
f[i][j][1]=min(C,D);
其中 \(sum\) 数组为消耗总量的前缀和，可以降低时间复杂度。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=55;
int n,c,x;
int p[N],sum[N],f[N][N][2];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
n=read();
c=read();
for(int i=1;i<=n;i++){
p[i]=read();
x=read();
sum[i]=sum[i-1]+x;
}
memset(f,INF,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;
int A=f[i+1][j][0]+(p[i+1]-p[i])*(sum[n]-sum[j]+sum[i]);
int B=f[i+1][j][1]+(p[j]-p[i])*(sum[n]-sum[j]+sum[i]);
int C=f[i][j-1][0]+(p[j]-p[i])*(sum[n]-sum[j-1]+sum[i-1]);
int D=f[i][j-1][1]+(p[j]-p[j-1])*(sum[n]-sum[j-1]+sum[i-1]);
f[i][j][0]=min(A,B);
f[i][j][1]=min(C,D);
}
}
printf("%d",min(f[1][n][0],f[1][n][1]));
return 0;
}