这个题目真的做的很惆怅。
拿到题目第一眼就知道是一个裸的区域动归。但是不晓得状态怎么转移。
一开始想的是状态表示的是当前范围内消耗的最小能量。
但是后来一想不行。于是才把状态表示为全局的消耗最小的能量。
dp[i][j][0]:在i到j范围内的灯都被点亮了，最后停在了j上，此时全局消耗的最小的能量
dp[i][j][1]:在i到j范围内的灯都被点亮了，最后停在了i上，此时全局消耗的最小的能量
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 1000000010
using namespace std;
int dp[1100][1100][2];
int s[1100];
int w[1100];
int d[1100];
int main()
{int n,v,i,j;while(~scanf("%d%d",&n,&v)){memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){scanf("%d%d",&d[i],&w[i]);s[i]=s[i-1]+w[i];}for(i=0;i<=n+1;i++){for(j=0;j<=n+1;j++)dp[i][j][0]=dp[i][j][1]=INF;}dp[v][v][0]=0;dp[v][v][1]=0;for(i=v;i<=n;i++){for(j=i-1;j>=1;j--){dp[j][i][0]=min(dp[j+1][i][0]+(d[j+1]-d[j])*(s[n]-(s[i]-s[j])),dp[j+1][i][1]+(d[i]-d[j])*(s[n]-(s[i]-s[j])));dp[j][i][1]=min(dp[j][i-1][1]+(d[i]-d[i-1])*(s[n]-(s[i-1]-s[j-1])),dp[j][i-1][0]+(d[i]-d[j])*(s[n]-(s[i-1]-s[j-1])));}}cout<<min(dp[1][n][0],dp[1][n][1])<<endl;}return 0;
}