你要考虑dp没有后效性
by vzcx_host @ 2022-08-28 18:14:29
也就是不应该有lt这个数组
by vzcx_host @ 2022-08-28 18:16:06
@[Hi_chocolate](/user/193198)
哇居然有NOI dalao来回答我这个蒟蒻的问题
但我还是贴一下代码吧
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long maxN=1000;
long long n,m;
long long f[maxN][maxN],lt[maxN][maxN],t[maxN];//f[i][j]表示第i~j车一起发车的最小花费
long long at[maxN],pj[maxN];
signed main(){
ios::sync_with_stdio(false);//cin加速
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);//再度加速
//不能用prlong longf,scanf
cin >> n >> m;
for(long long i=1;i<=n;i++){
cin >> t[i];
}
sort(t+1,t+n+1);
for(long long i=1;i<=n;i++){
at[i]=t[i];at[i]+=at[i-1];
}
for(long long i=1;i<=n;i++){
cout << t[i] << " ";
}cout << endl;
f[1][1]=0;
lt[1][1]=t[1];
for(long long i=2;i<=n;i++){
for(long long j=i;j>=1;j--){
lt[i][j]=0x7ffffff;
f[i][j]=0x7ffffff;
if(j==1){
long long s=t[i];
f[i][j]=s*(i-j+1)-(at[i]-at[j-1]);
lt[i][j]=t[i];
continue ;
}
for(long long k=j-1;k>=1;k--){
long long s=max(lt[j-1][k]+m,t[i]);
if(f[i][j]==s*(i-j+1)-(at[i]-at[j-1])+f[j-1][k]){
if(s<lt[i][j]){
lt[i][j]=s;
}
}
if(f[i][j]>s*(i-j+1)-(at[i]-at[j-1])+f[j-1][k]){
f[i][j]=s*(i-j+1)-(at[i]-at[j-1])+f[j-1][k];
lt[i][j]=s;
}
}
}
}
long long ans=0x7ffffff;
// for(long long i=1;i<=n;i++){
// for(long long j=i;j>=1;j--){
// cout << f[i][j] << " ";
// }cout << endl;
// }
for(long long i=1;i<=n;i++){
ans=min(f[n][i],ans);
}cout << ans << endl;
return 114514-114514;
}
/*
hello sir ,
make sure that you aren't writing in 空格式。
20 2
85 85 84 96 0 0 85 82 97 83 82 95 85 94 0 0 82 0 83 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 82 82 82 83 83 84 85 85 85 85 94 95 96 97
0 0 0 0 0 0 0 0 0 1 2 2 3 4 5 5 5 6 6 7
0 0 0 0 0 0 82 82 82 84 84 84 86 86 85 85 94 95 96 97
1 1 1 1 1 1 7 7 7 10 10 10 13 13 13 10 17 18 18 20
*/
```
by Benzenesir @ 2022-08-28 19:52:23
@[Hi_chocolate](/user/193198)
为什么不能有$lt$数组呢
by Benzenesir @ 2022-08-28 19:53:38
@[Benzenesir](/user/258178)
为了转移，你需要对于每个人都求出每一个他可能上车的时间点对应的f值，不然会存在后效性问题
显然对于时间i的人来说，他最迟会在i+m的时间上车，所以对于每个人求出他在i,i+1,...,i+m时间点即可，最坏 $O(n^2m)$
by vzcx_host @ 2022-08-28 21:39:37
@[Benzenesir](/user/258178)
$F_{i,j}=\max\{F_{i-1,k}+j\}$
其中 $t_{i-1}+k\le t_i+j$
时间复杂度 $O(nm^2)$
空间复杂度 $O(nm)$
by vzcx_host @ 2022-08-28 21:49:19
@[Benzenesir](/user/258178)
等等，条件改成 $t_{i-1}+k=t_i+j$ 或 $t_{i-1}+k+m\le t_i+j$
by vzcx_host @ 2022-08-28 21:53:36
@[Hi_chocolate](/user/193198)
谢谢dalao
by Benzenesir @ 2022-08-29 21:27:03