本文作者：Zhang, Xuheng
本文分类：编程学习笔记 浏览：1273
阅读时间：2636字, 约3-4.5分钟
题目链接：
https://www.luogu.com.cn/problem/P5017
这题难度飙升。。。
10分：
//10
#include <bits/stdc++.h>
using namespace std;
int main()
{
//freopen ("bus.in","r",stdin);
//freopen ("bus.out","w",stdout);
int n,m;
int a;
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a;
}
cout<<"0";
//fclose (stdin); fclose (stdout);
return 0;
} ↑骗分。
分析：
本题做法：动态规划！（DP）
首先将t数组升序排序
设f[i][j]表示第i个人等了j分钟的车，载完前i个人的最小等车时间总和。
j的取值范围？
由题可知，若车在人大附中停了m分钟，那么不如在到人大附中时先送走一批人（即便当时没人），所以停车时间T1<m
设一个人等到车从人民大学回来的时间为T2
因为车往返一次只需m分钟，所以T2<m
综上，一个人等车的时间
j=T1+T2<2m
该如何转移？
- 若下一个人能赶上当次车（即t[i]+j>=t[i+1]), 则将f[i][j]+t[i]+j-t[i+1]转移至f[i+1][t[i]+j-t[i+1]];
- 若下一个人在当次车回来之前开始等车（即t[i]+j+m>=t[i+1])， 则枚举车回来后停的时间k, 用f[i][j]+t[i]+j+m+k-t[i+1]转移f[i+1][t[i]+j+m+k-t[i+1]];
- 若下一个人在当次车回来之后才到（即t[i]+j+m<t[i+1]),则枚举下 一个人等待的时间k，并用f[i][j]+k转移f[i+1][k];
空间复杂度O(nm),时间复杂度O(nm^2)。
50 分的做法，时间复杂度为 O(t^2)。代码如下：
#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &ti); t = std::max(t, ti);
cnt[ti]++; sum[ti] += ti;
}
for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
for (int i = 0; i < t + m; i++)
{
f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
for (int j = 0; j <= i - m; j++) { f[i] = std::min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j])); }
}
for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
printf("%d\n", ans);
return 0;
}时间复杂度降至 O(tm)，可得 70 ~ 100不等的成绩
代码如下：
#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &ti); t = std::max(t, ti);
cnt[ti]++; sum[ti] += ti;
}
for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
for (int i = 1; i < t + m; i++) {
f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
for (int j = std::max(i - m - m + 1, 0)/*剪去无用转移*/; j <= i - m; j++) { f[i] = std::min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j])); }
}
for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
printf("%d\n", ans);
return 0;
}易知，随着 j的增大，能够转移的 k 的上限也不断增大，故使用前缀最小值维护可以转移的 gi−1, k。
时间复杂度为 O(n log n+nm)，即 O(nm)，目前看应该是最快的 dp做法了。注意边界细节，AC代码如下：
#include <cstdio>
#include <algorithm>
const int maxN = 505, maxM = 205;
int n, m, mm, ans = 1e9, t[maxN], g[maxN][maxM];
int main() {
scanf("%d%d", &n, &m); mm = m + m;
for (int i = 1; i <= n; i++) { scanf("%d", &t[i]); }
std::sort(t + 1, t + n + 1); // 排序.
for (int i = 1; i <= n; i++) {
g[i][0] = 1e9; // 先特判 j = 0 的情况.
for (int j = 0; j <= std::min(t[i] - t[i - 1] - m, m - 1); j++) { g[i][0] = std::min(g[i][0], g[i - 1][j]); }
for (int j = 1; j < mm; j++) { g[i][j] = std::min(g[i][j - 1], t[i] + j - t[i - 1] - m >= 0 && t[i] + j - t[i - 1] - m < mm ? g[i - 1][t[i] + j - t[i - 1] - m] : (int) 1e9); } // 前缀最大值维护新开一段的情况.
for (int j = 0; j < mm; j++) { g[i][j] = std::min(g[i][j], t[i] + j - t[i - 1] < mm ? g[i - 1][t[i] + j - t[i - 1]] : (int) 1e9) + j; } // 分在同一段内的情况, 加上 j 的贡献.
}
for (int i = 0; i < m; i++) { ans = std::min(ans, g[n][i]); }
printf("%d\n", ans);
return 0;
}注：本人在做的时候只得了50分。所以AC代码由洛谷用户https://www.luogu.com.cn/user/26673提供。
完结！！
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14