@[Fish_Clever](/user/104918) 我和你的思路一样不过我区间dp也WA了#6，#7，#10
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=60;
int c,w[maxn],n,dis[maxn],dp[maxn][maxn][2],g[maxn][maxn][2];
int dist(int x,int y){
return abs(dis[x]-dis[y]);
}
int main(){
memset(dp,0x3f,sizeof(dp));
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) scanf("%d%d",&dis[i],&w[i]);
for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=dist(i,c)*w[i],g[i][i][0]=g[i][i][1]=dist(i,c);
for(int d=2;d<=n;d++)
for(int i=1;i<=n-d+1;i++){
int j=i+d-1;
if(dp[i+1][j][0]+(dist(i+1,i)+g[i+1][j][0])*w[i]<dp[i+1][j][1]+(dist(i,j)+g[i+1][j][1])*w[i])
g[i][j][0]=(dist(i+1,i)+g[i+1][j][0]),dp[i][j][0]=dp[i+1][j][0]+g[i][j][0]*w[i];
else
g[i][j][0]=(dist(i,j)+g[i+1][j][1]),dp[i][j][0]=dp[i+1][j][1]+g[i][j][0]*w[i];
if(dp[i][j-1][1]+(dist(j-1,j)+g[i][j-1][1])*w[j]<dp[i][j-1][0]+(dist(i,j)+g[i][j-1][0])*w[j])
g[i][j][1]=(dist(j-1,j)+g[i][j-1][1]),dp[i][j][1]=dp[i][j-1][1]+g[i][j][1]*w[j];
else
g[i][j][1]=(dist(i,j)+g[i][j-1][0]),dp[i][j][1]=dp[i][j-1][0]+g[i][j][1]*w[j];
}
printf("%d",min(dp[1][n][0],dp[1][n][1]));
return 0;
}
```
by x17875487211 @ 2022-08-24 10:42:59