社区讨论

求证伪奇怪做法

P5017[NOIP 2018 普及组] 摆渡车参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m0qqy2rw
此快照首次捕获于
2024/09/06 21:23
2 年前
此快照最后确认于
2025/11/04 21:39
4 个月前
查看原帖
O(n3)O(n^3),思路是枚举该段右端点和上一段的右端点,然后记一个辅助的 fif_i 表示以 ii 为结尾,在取到最小等待时间的情况下,这段的车开车最早时间是多少,然后转移。
然而只有 25pts。
CPP
void solution(){
    int n, m; in >> n >> m;
    for(int i = 1; i <= n; i++) in >> t[i];
    sort(t + 1, t + n + 1);
    memset(dp, 0x3f, sizeof dp);
    memset(f, 0x3f, sizeof f);
    dp[0] = 0, f[0] = -1e18;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            LL st = max(f[j] + m, t[i]), c = 0;
            for(int k = j + 1; k <= i; k++){
                c += max(st - t[k], 0LL);
            }
            if(dp[j] + c < dp[i]){
                dp[i] = dp[j] + c, f[i] = st;
            } else if(dp[j] + c == dp[i] && st < f[i]){
                f[i] = st;
            }
        }
    }
    out << dp[n] << newl;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...