题目大意:
有n个人,住在一条直线上。第i个人的坐标是Xi,街上有个外卖餐馆的位置是X,现在餐厅工作人员要给街上的每个人送饭,送完之后再回到餐厅,送饭人的速度是V,每个人有个不满意值,当这个人送餐时间每晚一分钟,则这个人的不满意值增加Bi. 要求总的不满意值最小。
===============================================================================================================
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL INF = 1e9+;
const LL maxn = 1e3+;
const LL MOD = 1e9+;
int dp[][maxn][maxn], sum[maxn];
struct node
{
int X, B;
bool friend operator < (node A, node B)
{
return A.X < B.X;
}
} P[maxn]; int main()
{
int n, v, x;
while(cin >> n >> v >> x)
{
for(int i=; i<=n; i++)
cin >> P[i].X >> P[i].B;
P[n+].X = x, P[n+].B = ;
n ++;
memset(dp, , sizeof(dp));
memset(sum, , sizeof(sum));
sort(P+, P++n); sum[] = ;
for(int i=; i<=n; i++)
sum[i] = sum[i-] + P[i].B;
int Star; for(int i=; i<=n+; i++)
for(int j=; j<=n+; j++)
dp[][i][j] = dp[][i][j] = INF; for(int i=; i<=n; i++)
{
if(P[i].X == x)
{
Star = i;
break;
}
}
dp[][Star][Star] = dp[][Star][Star] = ;
for(int i=Star; i>=; i--)
for(int j=Star; j<=n; j++)
{
dp[][i][j] = min(dp[][i][j], dp[][i+][j] + (P[i+].X - P[i].X)*(sum[n]-sum[j]+sum[i]) );
dp[][i][j] = min(dp[][i][j], dp[][i+][j] + (P[j].X - P[i].X)*(sum[n]-sum[j]+sum[i]) ) ;
dp[][i][j] = min(dp[][i][j], dp[][i][j-] + (P[j].X - P[i].X)*(sum[n]-sum[j-]+sum[i-]) );
dp[][i][j] = min(dp[][i][j], dp[][i][j-] + (P[j].X - P[j-].X)*(sum[n] - sum[j-] + sum[i-]) );
}
printf("%d\n", min(dp[][][n],dp[][][n])*v);
}
return ;
}