题解 | #wyh的问题#

思路： 区间dp

设dp[l][r]表示[l,r]区间人在左端点里最小的耗电值

dp[r][l]表示[l,r]区间人在右端点的最小值

设起点为st

因为l<=st,r>=st所以这样设置dp不会有重叠的情况

然后就推方程啦

先用前缀和记录前i个电灯的每秒耗电量

同时可以注意到人在左端点的时候，可以是上一个左端点向左边走一步，也可以是右边的右端点走到了这个区间的左端点

那么方程就是

dp[l][r]=min(dp[l][r],dp[l+1][r]+(a[l+1]-a[l])×(sum[n]-sum[r]+sum[l]),dp[r][l+1]+(a[r]-a[l])×(sum[n]-sum[r]+sum[l]));

sum[n]-sum[r]+sum[l]表示[l+1,r]区间的每秒的耗电量

同理得

dp[r][l]=min(dp[r][l],dp[r-1][l]+(a[r]-a[r-1])×(sum[n]-sum[r-1]+sum[l-1]),dp[l][r-1]+(a[r]-a[l])×(sum[n]-sum[r-1]+sum[l-1]));

方程推出来了那我们就直接枚举起点左边的l和起点右边的r就好啦，最后选区间为[1,n]左端点或者右端点最小的输出

AC代码：

#include <string.h>
#define int long long
using namespace std;
int a[1010];
int dp[1010][1010];
int b[1010];
int sum[1010];
signed main()
{
    int n;
    while(cin>>n){
        memset(dp,0x3f3f3f3f,sizeof(dp));
        int st;
        cin>>st;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            sum[i]=sum[i-1]+b[i];
        }
        dp[st][st]=0;
        for(int l=st;l>=1;l--){
            for(int r=st;r<=n;r++){
                    int tot=sum[n]-sum[r]+sum[l];
                dp[l][r]=min(dp[l][r],min(dp[l+1][r]+(a[l+1]-a[l])*tot,dp[r][l+1]+(a[r]-a[l])*tot));
                dp[r][l]=min(dp[r][l],min(dp[r-1][l]+(a[r]-a[r-1])*(sum[n]-sum[r-1]+sum[l-1]),dp[l][r-1]+(a[r]-a[l])*(sum[n]-sum[r-1]+sum[l-1])));
            }
        }
        cout<<min(dp[1][n],dp[n][1])<<endl;
    }
    return 0;
}