路灯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;
}

JZTXT

刷题笔记（2023.9.22）

路灯2