https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18676
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18673
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| \section{错误七（TLE）：循环内 \texttt{vector} 拷贝构造导致 $10^7$ 次堆分配}
\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < N; ++i) {
ll ch = s[i] - '0';
vector<ll> ndp = dp; // 拷贝构造：每次都 new 一块内存
for (int status = 0; status <= 45; ++status) {
// ...
}
swap(ndp, dp);
} // ndp 析构：每次都 delete 一块内存
\end{minted}
\subsection*{错误分析}
\texttt{vector<ll> ndp = dp;} 是拷贝构造，每次调用都会在堆上分配 $50 \times 8 = 400$ 字节的新内存，循环结束时 \texttt{ndp} 析构又将其释放。$N$ 最大为 $10^7$，因此总共触发 $10^7$ 次 \texttt{malloc} + $10^7$ 次 \texttt{free}，系统调用开销远超 DP 本身的计算量。
\subsection*{修复}
将 \texttt{ndp} 的声明提到循环外部，循环内用赋值代替构造：
\begin{minted}{cpp}
vector<ll> ndp; // 提到循环外
for (int i = 0; i < N; ++i) {
ll ch = s[i] - '0';
ndp = dp; // 赋值：size 相同时不会重新分配内存
for (int status = 0; status <= 45; ++status) {
// ...
}
dp.swap(ndp); // O(1)，只交换内部指针
}
\end{minted}
|