——————————————————
题解背景
这道题真的好难啊！蒟蒻用了一个下午才AC！
QWQ ~~~~~
——————————————————
题意概括
有n个人想要从车站去学校，每个人都有一个到达车站的时间 a[i]
车站到学校只有一辆车，车来回时间为m
求将n个人送到学校的最少时间……
———————————————————
思路分析
蒟蒻最初看到这道题的时候，第一反应就是 排序 + DFS + 记忆化
下面是分析：
①排序：
根据 cookiebus 这位大佬所讲述的定律： ~~ 无序有解的题目有序一定有解 ~~
而且这种连我这种蒟蒻都知道要排序，大佬就不用多说了叭~~~~~~
②DFS： 根据 ml13 这位大佬所讲述的定律：
~~ 在dp的题目没有思路的时候，可以先暴力写DFS再转化思路 ~~
而且DFS也比较好理解，模拟每种情况即可
③记忆化：
那暴搜肯定是要TLE，而且dp有一个特性就是 ~~ 重叠子问题 ~~
我们可以记录子问题来达到记忆化的效果
④DFS怎么写：
定义一个DFS（l,r,t）表示 列车将在时间t时到站，然后将l~r的人全部带走的最小等待时间
那么我们只需要枚举一下 i （l <= i <= r） 表示先将 l~i的人送走，在回来接 i+1 ~ r 的方案 取最小值即可
初步代码实现（暴力DFS，30分代码）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn = 5e2 + 10;
int a[maxn], dp[maxn][maxn];
int n, m;
int DFS(int l, int r, int t) {
if (l == r) return max(t - a[l], (long long)0); //防止负数，和 0 取最大值
int ans = INT_MAX;
int cnt = 0;
for (int i = l; i <= r; i++) {
int tmp = 0;
for (int j = l; j <= i; j++) {
if (a[j] < max(t, a[i]))
tmp += max(t, a[i]) - a[j];
}
if (i + 1 <= r)
tmp += DFS(i + 1, r, max(t, a[i]) + m);
ans = min(ans, tmp);
}
return ans;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
cout << DFS(1, n, 0) << endl;
return 0;
}
思考优化
嘶~~~~蒟蒻交完以后发现只有30分，为什么呢？
可以发现枚举之后还有一重循环在计算时间！！！
仔细地大佬肯定还会发现 DFS 中 r 是 恒等于 n 的……
这样DFS函数内就有n^2的复杂度，还有多余参数，肯定是过不了的……
那么我们怎样优化呢？？？
很简单，直接根据数学原理去掉循环，再将 r 去掉 改成 n 即可
————————————————————
代码二次加工（加上记忆化也只有45分）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn = 5e2 + 10;
int a[maxn];
map<int, int> dp[maxn];
int n, m;
int DFS(int l, int t) {
if (l > n)
return 0;
if (l == n)
return max(t - a[l], (long long)0);
if (dp[l][t] != 0) //记忆化
return dp[l][t];
int cnt = 0;
int i = l;
while (a[i] <= t && i <= n) {
cnt += t - a[i];
i++;
}
int ans = cnt + DFS(i, t + m);
for (; i <= n; i++) {
cnt += (i - l) * (a[i] - max(a[i - 1], t)); //由于作者很懒，数学原理懒得讲，自行细品
int tmp = cnt;
if (i + 1 <= n)
tmp += DFS(i + 1, max(t, a[i]) + m);
ans = min(ans, tmp);
}
return dp[l][t] = ans;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
cout << DFS(1, 0) << endl;
return 0;
}
继续思考
为什么加了记忆化还是只有45分呢？
可以发现 时间是可以非常大的（详细见数据范围），情况一多，记忆化并没有特别的功效………………
蒟蒻陷入了沉思……………………
最后蒟蒻想出：
t-a[i] 可以作为等待时间这个参数来记忆化！！！（本人比较懒，其中过程自行补足）
那么就可以完成最后代码了！！！
——————————————————————
AC代码（终于可以AC了）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn=5e2+10;
int a[maxn];
map <int,int> dp[maxn];
int n,m;
int DFS(int l,int t){
if(l > n) return 0;
if(l == n) return max(t-a[l],(long long)0);
if(t < a[l])return DFS(l,a[l]); //防止RE
if(dp[l][t - a[l]] != 0)return dp[l][t - a[l]];
int cnt=0;
int i=l;
while(a[i] <= t && i <= n){
cnt += t - a[i];
i++;
}
int ans = cnt + DFS(i,t+m);
for(;i<=n;i++){
cnt += (i - l) * (a[i] - max(a[i-1],t));
int tmp = cnt;
if(i+1 <= n) tmp+=DFS(i+1,max(t,a[i])+m);
ans = min(ans,tmp);
}
return dp[l][t - a[l]] = ans;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
cout<<DFS(1,0)<<endl;
return 0;
}
芜湖！完结撒花！！！