前言
这题还是有点意思的。
题意： 给你 (n) （(n<=3000)） 个弹珠，它们位于数轴上。给你弹珠的坐标 (x_i) 在弹珠 (i) 上面花费 (C_i) 的钱 可以使弹珠在原地不动 ((-10^9<=x_i,C_i<=10^9))，游戏开始时，所有的弹珠向左滚动，直到碰到定在原地不动的弹珠，其花费是其滚动的距离。总花费=开始前的花费+弹珠滚动的花费，问最小的花费是多少
题解
首先划分出阶段,，我们可以先将弹珠排序，前 (i) 个弹珠，最后一个固定的弹珠是 (j) ((j<i))
(=>) 设 (f_{i,j}) 表示 前 (i) 个弹珠，最后一个固定的弹珠是 (j) ((j<i)) 的最小花费
可以这样想，当最后一个定点 (j) 在 (i) 时，是不是就要在 (i) 的前面找到一个最小的定点继承 所以要找 (1<=k<i) 中 (f_{i-1,k}) 最小的这个点，然后加上定 (i) 点的花费
而当最后一个定点 (j) 不在 (i) 时 只要在 (f_{i-1,j}) 的基础上加上点 (i) 到点 (j) 的距离
转移：
-
(f_{i,j}=min{f_{i-1,k}} + C_i (i==j))
-
(f_{i,j}=f_{i-1,j}+x_i-x_j (j<i))
Code
// int下INF=0x3f3f3f3f
// long long 下 INF=1e19
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
#define INF 1e19
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 3007;
int n;
int f[N][N];
struct Marbles { //弹珠
int x,c;
}a[N];
bool cmp(Marbles x,Marbles y) {
return x.x < y.x;
}
signed main()
{
n = read();
for(int i=1;i<=n;++i)
a[i].x = read(), a[i].c = read();
sort(a+1, a+1+n, cmp);
int minn;
f[1][1] = a[1].c;
for(int i=2;i<=n;++i) {
minn = INF;
for(int j=1;j<i;++j) {
f[i][j] = f[i-1][j] + a[i].x - a[j].x;
minn = min(minn, f[i-1][j]);
}
f[i][i] = minn + a[i].c;
}
int ans = INF;
for(int i=1;i<=n;++i)
ans = min(ans, f[n][i]);
cout<<ans<<endl;
return 0;
}