洛谷1220 关路灯

Luogu

分析

设$f[i][j][0]$表示$i$到$j$的路灯、最后关$i$最小用电量,$f[i][j][1]$表示$i$到$j$的路灯、最后关$j$最小用电量。
那么答案为 $min(f[1][n][1],f[1][n][n])$
用前缀和数组sum来记录电量,则可以在O(1)时间内算出区间电量和。

容易转移:

$f[i][j][0]=min((a[i+1]-a[i])*(sum[n]-sum[j]+sum[i])+f[i+1][j][0],\\(a[j]-a[i])*(sum[n]-sum[j]+sum[i])+f[i+1][j][1])$
$f[i][j][1]=min((a[j]-a[j-1])*(sum[n]-sum[j-1]+sum[i-1])+f[i][j-1][1],\\(a[j]-a[i])*(sum[n]-sum[j-1]+sum[i-1])+f[i][j-1][0])$

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int f[60][60][2];
int p[60],w[60],sum[60];
int main()
{
    int n,c;
    scanf("%d%d",&n,&c);
    for (int i=1;i<=n;i++) //输入+前缀和 
    {
        scanf("%d%d",&p[i],&w[i]);
        sum[i]=sum[i-1]+w[i];
    }
    for (int i=1;i<=n;i++) f[i][i][0]=f[i][i][1]=sum[n]*abs(p[i]-p[c]); //边界 
    for (int l=2;l<=n;l++) //核心DP部分  
        for (int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            f[i][j][0]=min((p[i+1]-p[i])*(sum[n]-sum[j]+sum[i])+f[i+1][j][0],
            (p[j]-p[i])*(sum[n]-sum[j]+sum[i])+f[i+1][j][1]);
            f[i][j][1]=min((p[j]-p[j-1])*(sum[n]-sum[j-1]+sum[i-1])+f[i][j-1][1],
            (p[j]-p[i])*(sum[n]-sum[j-1]+sum[i-1])+f[i][j-1][0]);
        }
    printf("%d\n",min(f[1][n][0],f[1][n][1])); //输出  
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 06 PM

发表评论