题面
1.前言
我记得这是上上上…(此处省略多个“上”字) 次考试的题了，结果我思路想到了，但是没打出来(因为我脑子what了，只用一个变量去完成人家两个数组完成的事，代码十分麻烦，细节也多)，这次又双叒花了很长时间去debug。 我爱死这个摆渡车了，以后我出去都坐摆渡车
2.分析
状态: dp[i]表示在i这个时刻，车在人大附中，最小的等车时间和 易得 状态转移方程为：
d
p
[
i
]
=
m
i
n
(
d
p
[
j
]
+
[
j
,
i
]
时
刻
之
间
的
等
车
时
间
和
)
(
0
<
=
j
<
i
)
dp[i] = min (dp[j] + [j, i]时刻之间的等车时间和) (0 <= j < i)
dp[i]=min(dp[j]+[j,i]时刻之间的等车时间和)(0<=j<i)
时间复杂度:
O
(
n
∗
n
∗
n
)
O(n * n * n)
O(n∗n∗n)
伪代码
for (i
: 1 ~ n
) {
for (j
: 1 ~ i
- 1) {
int cnt
= 0;
for (k
: j
~ i
) {
cnt
+= k时刻到来的人所需等待的时间
}
dp
[i
] = min
(dp
[i
], dp
[j
] + cnt
);
}
}
ATTENTION: 最终的答案不在
d
p
[
m
a
x
(
t
[
i
]
)
]
dp[max(t[i])]
dp[max(t[i])] 里，因为将时间第二大的人送走后返回到人大附中的时间是
第
二
大
的
时
间
+
m
第二大的时间 + m
第二大的时间+m ，所以答案应该为
m
i
n
(
d
p
[
i
]
)
(
m
a
x
(
t
[
j
]
)
<
=
i
<
m
a
x
(
t
[
j
]
)
+
m
)
min (dp[i]) ( max (t[j]) <= i < max (t[j]) + m)
min(dp[i])(max(t[j])<=i<max(t[j])+m)
3.优化
1.我们先分析车，车的停留时间是不会超过m的（因为Ta可以在相同的状态下多跑一趟，这肯定比少跑一趟的结果优）
2.我们能不能用更快的时间去计算出[j, i]时刻之间的等车时间和呢？答案是可以的，我们可以用一个前缀和数组来实现，具体操作见下
for (int i
= 1; i
<= n
; i
++) {
scanf
("%lld", &a
[i
]);
r
= Max
(r
, a
[i
]);
prenum
[a
[i
]]++; pret
[a
[i
]] += a
[i
];
}
for (int i
= 1; i
< r
+ m
; i
++) prenum
[i
] += prenum
[i
- 1], pret
[i
] += pret
[i
- 1];
(prenum
[i
] - prenum
[j
]) * i
- (pret
[i
] - pret
[j
])即为
[j
, i
]时刻之间的等车时间和
4.代码
#include <cstdio>
#define LL long long
const int MAXN
= 505;
const int MAXT
= 5 * 1e6 + 5;
int n
, m
;
LL r
;
LL a
[MAXN
], prenum
[MAXT
], pret
[MAXT
], dp
[MAXT
];
LL Max
(LL x
, LL y
) { return x
> y
? x
: y
; }
LL Min
(LL x
, LL y
) { return x
< y
? x
: y
; }
int main
() {
scanf
("%d %d", &n
, &m
);
for (int i
= 1; i
<= n
; i
++) {
scanf
("%lld", &a
[i
]);
r
= Max
(r
, a
[i
]);
prenum
[a
[i
]]++; pret
[a
[i
]] += a
[i
];
}
if (m
== 1) {
printf
("0");
return 0;
}
for (int i
= 1; i
< r
+ m
; i
++) prenum
[i
] += prenum
[i
- 1], pret
[i
] += pret
[i
- 1];
for (int i
= 1; i
< r
+ m
; i
++) {
dp
[i
] = i
* prenum
[i
] - pret
[i
];
for (int j
= Max
(i
- m
* 2 + 1, 0); j
<= i
- m
; j
++) {
dp
[i
] = Min
(dp
[i
], dp
[j
] + (prenum
[i
] - prenum
[j
]) * i
- (pret
[i
] - pret
[j
]));
}
}
LL ans
= 0x7f7f7f7f7f7f7f;
for (int i
= r
; i
< r
+ m
; i
++) ans
= Min
(ans
, dp
[i
]);
printf
("%lld", ans
);
return 0;
}
注：我这个代码用C++(NOI)提交， 就算 不择手段的 优化，Ta也过不了，若诸位大佬有更好的算法，请不吝赐教。 orz
