自动搬运

查看原文

来自洛谷，原作者为

	z2415445508 None

搬运于2025-08-24 21:22:34，当前版本为作者最后更新于2017-09-21 09:52:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道区间型的动态规划题；

我主要是对前方的一些dp题解补充一些小细节。

既然是动规，那么首先讲一下常用的填表法和刷表法：

填表法就是利用状态转移方程和上一个状态来推导出现在的状态（相当于知道已知条件，将答案填入）

刷表法就是利用当前的状态，把有关联的下一状态都推出来。

这道题我选用的是填表法。

理解一下题目大意：

关灯不需要额外的时间，经过了灯就关了。但是可能折返回去关某一个大灯会比继续往下走关接下来的一个小灯更优，

那么可以得到两种状态（沿着当前方向继续往下走，改变方向回去关灯）。

我们需要得到的整个关灯过程中的最优值（最小耗能）

那么要设计的状态转移方程中肯定有两种方案（折返的，不撞墙不回头的）

又因为如果想要关某一区间的灯的过程中耗能最小，所以可以转换成一个个区间来写：

去关某一区间的灯，那么整条街道上除了这一区间的灯会逐渐灭掉其他肯定会全亮。

那么我们把f[i][j]记为当从i到j的灯都熄灭后剩下的灯的总功率。

再进一步：f[i][j][0]表示关掉i到j的灯后，老张站在i端点，f[i][j][1]表示关掉[i][j]的灯后,老张站在右端点

（i为左端点，j为右端点）

又f[i][j][0]会由两种方案推导而来（上面有写。）：折返回来关i,j的灯、由i+1深入，继续关第i盏灯从而扩展到（i,j）；

所以得到状态转移方程：

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

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

（枚举现在的路灯l（2-n,因为第c位的路灯已经被关了），i+l-1<=n（路只有这么长），j=i+l-1（右端点））

因为最后不知道老张到底站在左端点最优还是站在右端点最优

所以在f[1][n][0]和f[1][n][1]中取min输出。

下附代码（含解释）

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXM=60;
int a[MAXM],b[MAXM],sum[MAXM],n,m,c;
int f[MAXM][MAXM][2];
int min(int a,int b)//这一点希望大家注意：最好max和min函数自己写，会有效的加快程序速度
{return a<b?a:b;}
int max(int a,int b)
{return a>b?a:b;}
int main()
{
  scanf("%d%d",&n,&c);
  memset(f,127,sizeof(f));//赋成极大值防止后面的min出问题
  for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]),sum[i]=sum[i-1]+b[i];
  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;
    f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]),//继续走下去会更快吗？
               f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));//还是从j点折返回来会更快？（此时假设[i+1][j]被关，i亮，从j端点往回赶去关i）
//要注意的一点是sum[n]-(sum[j]-sum[i])是包括了i这一点的电能的，因为走过来的过程中灯i也会耗电
    f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]),//同上
               f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
        }
  int ans=min(f[1][n][0],f[1][n][1]);
  printf("%d",ans);
  return 0;
}