本文共 1161 字，大约阅读时间需要 3 分钟。

区间dp，dp[i][j][0]表示关完第i到第j的灯之后在第i个灯的最小功耗，dp[i][j][1]表示关完第i到第j的灯之后在第j个灯的最小功耗。对于dp[i][j][1]一定优先是由i到j-1转移过来功耗最小，对于dp[i][j][0]一定是由i+1到j转移过来功耗最小。究竟有没有在转移时回头我们不能确定。我们要计算出所有灯的前缀和sum[i]来方便维护dp，所以状态转移方程为：

dp[s][e][1]=min(dp[s][e-1][0]+(x[e]-x[s])(sum[n]-sum[e-1]+sum[s-1]),dp[s][e-1][1]+(x[e]-x[e-1])(sum[n]-sum[e-1]+sum[s-1]));

#include
   
    using namespace std;const int maxn=57;int dp[maxn][maxn][5];int sum[maxn];int n,c,x[maxn],y[maxn];int main(){
       memset(dp,0x3f,sizeof(dp));    scanf("%d%d",&n,&c);    for(int i=1;i<=n;i++)    {
           cin>>x[i];        cin>>y[i];        sum[i]=sum[i-1]+y[i];    }    dp[c][c][0]=dp[c][c][1]=0;    for(int l=2;l<=n;l++)    for(int s=1;s+l-1<=n;s++)    {
           int e=s+l-1;        dp[s][e][0]=min(dp[s+1][e][0]+(x[s+1]-x[s])*(sum[n]-sum[e]+sum[s]),dp[s+1][e][1]+(x[e]-x[s])*(sum[n]-sum[e]+sum[s]));        dp[s][e][1]=min(dp[s][e-1][0]+(x[e]-x[s])*(sum[n]-sum[e-1]+sum[s-1]),dp[s][e-1][1]+(x[e]-x[e-1])*(sum[n]-sum[e-1]+sum[s-1]));    }    printf("%d\n",min(dp[1][n][1],dp[1][n][0]));    return 0;}
   

转载地址：http://hsgwi.baihongyu.com/