反思一下没有想出来……思维固化了……
设(dp[i][j][0/1])表示区间( ext{[i,j]})全部关灯，且停止在((i->0,j->1))位置的最小花费。
那么，(dp[i][j][0])由(dp[i+1][j][0/1])转移，(dp[i][j][1])由(dp[i][j-1][0/1])转移。
注意一下，我们求的是关上区间( ext{[i,j]})的最小耗能。所以，我们每关上一盏灯，所用的时间要计算到其它所有没有关的灯上面去。
也就是说，每次要累计的答案，不仅仅是你关上这盏灯所要耗费的能量。
由于我们是没更新，或者说每关上一盏灯统计一下本次关灯耗费的时间所导致的消耗，所以不会造成算重。
接着注意到，这个方程，转移顺序是( ext{i+1 to i,j-1 to j}),所以枚举的时候(i)必然倒序，(j)必然顺序。
考虑怎么枚举。
显然我们已经知道的是(C)的答案，即老爷子的起始位置。所以我们的答案应该是基于这个位置去扩散的。
而且注意到(i,j)应该从(C)开始，所以，如果我们：
(i=C o 1,j=i o n)的话，我们的(dp)数组是可以得到正确更新的。
还有另一种方式：可以先枚举(j).
枚举：(j=C o n,i=j-1 o 1),同样解决问题。
于是，两份代码都可以喜提(color{green}{AC}).
#include<bits/stdc++.h>
using namespace std;
int n,c;
int a[500],w[500],p[500];
int dp[51][51][2];
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&w[i]);
p[i]=p[i-1]+w[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dp[i][j][1]=dp[i][j][0]=99999;
dp[c][c][1]=dp[c][c][0]=0;
for(int i=c;i>=1;--i){
for(int j=i+1;j<=n;++j){
dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*(p[i]+p[n]-p[j]),
dp[i+1][j][1]+(a[j]-a[i])*(p[i]+p[n]-p[j]));
dp[i][j][1]=min(dp[i][j-1][1]+(a[j]-a[j-1])*(p[i-1]+p[n]-p[j-1]),
dp[i][j-1][0]+(a[j]-a[i])*(p[i-1]+p[n]-p[j-1]));
}
}
printf("%d
",min(dp[1][n][1],dp[1][n][0]));
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,c;
int a[500],w[500],p[500];
int dp[51][51][2];
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&w[i]);
p[i]=p[i-1]+w[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dp[i][j][1]=dp[i][j][0]=99999;
dp[c][c][1]=dp[c][c][0]=0;
for(int j=c;j<=n;++j){
for(int i=j-1;i>=1;--i){
dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*(p[i]+p[n]-p[j]),
dp[i+1][j][1]+(a[j]-a[i])*(p[i]+p[n]-p[j]));
dp[i][j][1]=min(dp[i][j-1][1]+(a[j]-a[j-1])*(p[i-1]+p[n]-p[j-1]),
dp[i][j-1][0]+(a[j]-a[i])*(p[i-1]+p[n]-p[j-1]));
}
}
printf("%d
",min(dp[1][n][1],dp[1][n][0]));
return 0;
}
两份代码的枚举顺序是不同的，但都过了。
总结：(DP)的时候，首先注意状态的设计，然后注意状态从哪里推出；再考虑这样(DP)的枚举方式。
反思。菜是原罪