社区讨论
求证伪奇怪做法
P5017[NOIP 2018 普及组] 摆渡车参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m0qqy2rw
- 此快照首次捕获于
- 2024/09/06 21:23 2 年前
- 此快照最后确认于
- 2025/11/04 21:39 4 个月前
,思路是枚举该段右端点和上一段的右端点,然后记一个辅助的 表示以 为结尾,在取到最小等待时间的情况下,这段的车开车最早时间是多少,然后转移。
然而只有 25pts。
CPPvoid 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 条回复,欢迎继续交流。
正在加载回复...