P1220 关路灯

· · 题解

由题意，这也是一道典型的区间dp

dp4步走

1：定义状态

dp[l][r][0/1]表示l~r的路灯全灭掉并且最后停在l/r的最小消耗

2：状态转移方程

dp[l][r][0]=min(dp[l+1][r][0]+(a[l+1]-a[l])(s[n]-s[r]+s[l]),dp[l+1][r][1]+(a[r]-a[l])(s[n]-s[r]+s[l]));//停在l

dp[l][r][1]=min(dp[l][r-1][0]+(a[r]-a[l])(s[n]-s[r-1]+s[l-1]),dp[l][r-1][1]+(a[r]-a[r-1])(s[n]-s[r-1]+s[l-1]));//停在r

停在l的状态转移方程可能由l+1或r转移而来 停在r的状态转移方程可能由r-1或l转移而来 而每次转移的消耗=上一次的位置到这一次的位置的绝对值（路程）*每一秒的消耗量

3：初始化

因为要求最小值（最小消耗量）所以要赋值最大值 memset(dp,0x3f,sizeof(dp));

而len==1的情况 （l==r）时不合法

所以不用做任何操作

4：答案

最后关完所有路灯后可能停在1/n so: cout << min(dp[1][n][0],dp[1][n][1]);//最小值

5：注意

为了节约时间 本体需要对消耗做一个前缀和

而初始位置 c 需要赋值为0 dp[c][c][0]=dp[c][c][1]=0;//不用消耗能量

附上代码：


#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
    int sum=0,f=1;
    char ch=getchar();
    while (ch<'0' || ch>'9'){
        if (ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while (ch>='0' && ch<='9'){
        sum=sum*10+ch-48;
        ch=getchar();
    }
    return sum*f;
}
void print(int x){
    if (x<0){
        putchar('-');
        x=-x;
    }
    if (x>9){
        print(x/10);
    }
    putchar(x%10+48);
    return;
}
long long dp[100][100][3];// dp[i][j][0/1]考虑i~j路灯全灭掉并且停在i/j的最小消耗 
long long a[100];
long long w[100];
long long s[100];
int main(){
    long long n,c;
    cin >> n >> c;
    for (int i=1;i<=n;i++){
        cin >> a[i] >> w[i];
    }
    for (int i=1;i<=n;i++){
        s[i]=s[i-1]+w[i];//前缀和 
    }
    memset(dp,0x3f,sizeof(dp));//求最小值赋值最大值 
    dp[c][c][0]=dp[c][c][1]=0;//初始位置 
    for (int len=1;len<=n;len++){//长度 
        for (int l=1;l+len-1<=n;l++){//起点 
            long long r=l+len-1;//终点 
            if (len==1){//不用赋值 
                //不合法 
            }
            else{
                dp[l][r][0]=min(dp[l+1][r][0]+(a[l+1]-a[l])*(s[n]-s[r]+s[l]),dp[l+1][r][1]+(a[r]-a[l])*(s[n]-s[r]+s[l]));//停在i 
                dp[l][r][1]=min(dp[l][r-1][0]+(a[r]-a[l])*(s[n]-s[r-1]+s[l-1]),dp[l][r-1][1]+(a[r]-a[r-1])*(s[n]-s[r-1]+s[l-1]));//停在j 
            }
        }
    }
    cout << min(dp[1][n][0],dp[1][n][1]);//停在1/n的最小功耗 
    return 0;
}

新手小白，请多多指教