- it
- Food Delivery（区间 dp）
Food Delivery
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std
;
#define ll long long
#define inf 0x3f3f3f3f
ll sum
[1200], dp
[1200][1200][2];
struct node
{
int dis
, b
;
} s
[1200];
bool
cmp(node x
, node y
) {
return x
.dis
< y
.dis
;
}
int main() {
int n
, v
, x
;
while (scanf("%d%d%d", &n
, &v
, &x
) != EOF) {
sum
[0] = 0;
for (int i
= 1; i
<= n
; i
++) {
scanf("%d%d", &s
[i
].dis
, &s
[i
].b
);
}
memset(dp
, inf
, sizeof(dp
));
sort(s
+ 1, s
+ n
+ 1, cmp
);
for (int i
= 1; i
<= n
; i
++) {
sum
[i
] = sum
[i
- 1] + s
[i
].b
;
}
for (int i
= 1; i
<= n
; i
++) {
dp
[i
][i
][0] = dp
[i
][i
][1] = abs(s
[i
].dis
- x
) * sum
[n
];
}
for (int len
= 2; len
<= n
; len
++) {
for (int i
= 1; i
+ len
<= n
+ 1; i
++) {
int j
= i
+ len
- 1;
dp
[i
][j
][0] = min(dp
[i
][j
][0],
dp
[i
+ 1][j
][0] + abs(s
[i
+ 1].dis
- s
[i
].dis
) * (sum
[n
] - sum
[j
] + sum
[i
]));
dp
[i
][j
][0] = min(dp
[i
][j
][0], dp
[i
+ 1][j
][1] + abs(s
[j
].dis
- s
[i
].dis
) * (sum
[n
] - sum
[j
] + sum
[i
]));
dp
[i
][j
][1] = min(dp
[i
][j
][1],
dp
[i
][j
- 1][0] + abs(s
[j
].dis
- s
[i
].dis
) * (sum
[n
] - sum
[j
- 1] + sum
[i
- 1]));
dp
[i
][j
][1] = min(dp
[i
][j
][1],
dp
[i
][j
- 1][1] + abs(s
[j
].dis
- s
[j
- 1].dis
) * (sum
[n
] - sum
[j
- 1] + sum
[i
- 1]));
}
}
printf("%d\n", min(dp
[1][n
][0], dp
[1][n
][1]) * v
);
}
}
