题解：CF38E Let's Go Rolling!

LIUYIFAN5 · 2025-12-02 09:15:42 · 题解

题意

有 n 个弹珠，对于第 i 个弹珠，有两种选择：

1. 定住，花费 c_i。
2. 不定，花费为这个弹珠到左侧第一个定住弹珠的距离，设这个左侧第一个定住弹珠为 j，即花费为 x_i-x_j。

思路

一眼线性 dp。

考虑分类讨论每一个弹珠定住或是不定住的情况，这里我定义了两个 dp 数组。

定义 dp_{i,j} 为第 i 个弹珠（不定住），上一个定住的弹珠位置在 j 的最小花费，f_{i} 表示第 i 个弹珠定住的最小花费。

这个定义想到是不难的，转移式子也不难想。

可以先尝试自己写写看再看代码。

做法

这样做是 O(n^3) 的，考虑优化：很简单 上面这段 \sum_{k=j+1}^{i} (x_k-x_j) 前缀和拆掉即可。

不妨令 s_i 表示 \sum_{k=1}^{i} x_i。

则 dp_{i,j}= \min(dp_{i,j},f_{j}+(s_i-s_j)-x_j \times (i-j))。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dp[3005][3005],f[3005],s[3005],ans=1e18;
struct node{
    int x,c;
}a[3005];
bool cmp(node p,node q){
    return p.x<q.x;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].c; 
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i].x;
    memset(dp,0x3f,sizeof(dp));
    memset(f,0x3f,sizeof(f)); 
    f[1]=a[1].c; 
    dp[1][1]=a[1].c;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i][j]=min(dp[i][j],f[j]+(s[i]-s[j])-a[j].x*(i-j));
//          cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            if(j==i-1)f[i]=min(f[i],f[j]+a[i].c);
            else f[i]=min(f[i],dp[i-1][j]+a[i].c); 
        }
        //cout<<f[i]<<" ";
    }
    for(int i=1;i<n;i++){
        ans=min(ans,dp[n][i]);
    }
    cout<<min(ans,f[n]);
}