题目的意思是给你一个机器人，初始的时候在某一个给定的路灯位置，机器人要把路边所有的路灯关掉，每个路灯都有一个距离和一个功率，求要把所有的路灯关掉最小的最终能耗是多少？
题目是一个很明显的区间DP。可以这样考虑，机器人关掉一个区间的路灯后，一定停留在该区间的最左端或者最右端，而且必须包括起点，显然。
这样我们就可以区间dp了。
对于每一个含有初始位置的区间[i,j]，只有两种位置使其最终的位置为j，那就是i和j-1。这样就得到了状态转移了。
接下来还有一个问题，就是怎么计算能耗呢？这样想，对于每个状态，表示关闭该区间的所有的灯后根据其所停留的位置，所有路灯的最小能耗总和。
所以我们可以对于每个路灯，用一个数组表示前面n个路灯的功耗总和，这样就可以dp了。
上代码：（效率还挺高的）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define maxn 1010 5 using namespace std; 6 7 int f[2][maxn][maxn],w[maxn],d[maxn],n,k,tep,tep1,tep2; 8 9 int main() 10 { 11 while (scanf("%d",&n)!=EOF) 12 { 13 scanf("%d",&k); 14 for (int i=1; i<=n; i++) scanf("%d%d",&d[i],&w[i]),w[i]+=w[i-1]; 15 memset(f,0x3f,sizeof f); 16 f[1][k][k]=f[0][k][k]=0; 17 for (int i=k; i>0; i--) 18 for (int j=k; j<=n; j++) 19 { 20 if (i==j) continue; 21 tep=w[n]-w[j]+w[i]; 22 tep1=tep*(d[i+1]-d[i])+f[0][i+1][j]; 23 tep2=tep*(d[j]-d[i])+f[1][i+1][j]; 24 f[0][i][j]=min(tep1,tep2); 25 tep=w[n]-w[j-1]+w[i-1]; 26 tep1=tep*(d[j]-d[j-1])+f[1][i][j-1]; 27 tep2=tep*(d[j]-d[i])+f[0][i][j-1]; 28 f[1][i][j]=min(tep1,tep2); 29 } 30 printf("%d ",min(f[0][1][n],f[1][1][n])); 31 } 32 return 0; 33 }