专栏文章

题解：CF1787C Remove the Bracket

OO_Yeee
CF1787C题解参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mio5byme
此快照首次捕获于
2025/12/02 13:37
3 个月前
此快照最后确认于
2025/12/02 13:37
3 个月前
查看原文
题目传送门。
首先观察最终求解的这个式子： F=a1⋅x2+y2⋅x3+y3⋅x4+y4⋅…⋅xn−1+yn−1⋅anF = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + y_4 \cdot \ldots \cdot x_{n-1}+y_{n-1} \cdot a_n 一个贪心是显而易见的：因为我们要使 FF 最小，所以就要使每个 xix_i 和 yiy_i 尽量的小。
而 (xi−s)⋅(yi−s)≥0(x_i-s) \cdot (y_i-s)\geq 0。这就告诉我们：我们选 xix_i 和 yiy_i 的时候要尽量靠近这个 ss 。所以说每个 ximinx_{i_{min}} 和 yiminy_{i_{min}} 就为 ai−sa_i-s 或 ss。
但是简单的贪心并不适用于这个题，因为若贪心策略是你每次选择最小的那个数，显然有： minni−1×minni+maxxj−1×maxxj≮minni−1×maxxj−1+minni×maxxjminn_{i-1} \times minn_{i} + maxx_{j-1} \times maxx_{j} \nless minn_{i-1}\times maxx_{j-1}+minn_{i} \times maxx_{j} （即小数 * 小数 + 大数 * 大数 不一定优于 小数 * 大数 + 小数 * 大数）
所以我们只能用其他方法做。
继续观察原式我们可以发现它满足 dpdp 的条件：
  1. 当取到第 ii 个数时，决策只与前面的值有关，并且在选了这个数后在当前一定最优。
  2. 每次选只与前面一项有关系。
其实用一个图更好理解：（图丑见谅）
可以发现在每次的答案只与 xi+1x_{i+1} 和 yiy_{i} 有关 所以我们可以设出 dpdp 状态。
令 dpi,0/1dp_{i,0/1} 表示在 ii 位置时 xx 取 ai−sa_i-s 还是 ss。
由上面的图可以清晰发现转移式子非常好想。 dpi,0=min⁡(dpi−1,0+yi,1×xi+1,0,dpi−1,1+yi,0×xi+1,0) dp_{i,0}=\min(dp_{i-1,0}+y_{i,1} \times x_{i+1,0},dp_{i-1,1}+y_{i,0} \times x_{i+1,0}) 即为上一个的和加上这一次取 ss 值 或取 ai−sa_i-s 值的最小值。
dpi,1dp_{i,1} 同理。 dpi,1=min⁡(dpi−1,0+yi,1×xi+1,1,dpi−1,1+yi,0×xi+1,1) dp_{i,1}=\min(dp_{i-1,0}+y_{i,1} \times x_{i+1,1},dp_{i-1,1}+y_{i,0} \times x_{i+1,1})
最后 dpn,0dp_{n,0} 和 dpn,1dp_{n,1} 取 minmin 即为答案。
有一个疑问可能是若 s+1s+1 和 ai−s−1a_i-s-1 比 ss 和 aia_i 更优的话怎么办，那样一定可以优化为 ai−sa_i-s 和 ss 这种情况，我们的 xi,0,yi,0,xi,1,yi,1x_{i,0},y_{i,0},x_{i,1},y_{i,1} 保证了这两种情况一定会讨论到，就没有问题。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N],dp[N][2],x[N][2],y[N][2];
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    return x*f;
}
void Main(){
    //cf多测千万不要用，会TLE
    // memset(a,0,sizeof(a));
    // memset(dp,0,sizeof(dp));
    // memset(x,0,sizeof(x));
    // memset(y,0,sizeof(y));
    int n,s;
    n=read(),s=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=2;i<n;i++){
        if(a[i]>=s)
        {
            x[i][0]=s,x[i][1]=a[i]-s;
            y[i][0]=s,y[i][1]=a[i]-s;
        }
        else {
            x[i][0]=a[i],x[i][1]=0;//注意<0时要特判
            y[i][0]=a[i],y[i][1]=0;
        }
        dp[i][0]=dp[i][1]=0;
    }
    y[1][0]=y[1][1]=a[1];
    x[n][0]=x[n][1]=a[n];//注意初始化
    for(int i=1;i<n;i++){
        dp[i][0]=min(dp[i-1][0]+y[i][1]*x[i+1][0],dp[i-1][1]+y[i][0]*x[i+1][0]);
        dp[i][1]=min(dp[i-1][0]+y[i][1]*x[i+1][1],dp[i-1][1]+y[i][0]*x[i+1][1]);
    }
    printf("%lld\n",min(dp[n-1][0],dp[n-1][1]));
}
signed main(){
    int T;T=read();
    while(T--)Main();
    return 0;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...