2020-2021:teams:alchemist:weekly_digest_10
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_10 [2020/08/14 17:49] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_10 [2020/08/14 22:11] (当前版本) maxdumbledore |
||
|---|---|---|---|
| 行 89: | 行 89: | ||
| - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ | - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ | ||
| - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (j<L[i] \lor j>R[i])$ | - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (j<L[i] \lor j>R[i])$ | ||
| - | - $dp[i][j][0/1]=dp[i-1][j][0/1]*2+(j-L[i]^2)\ (L[i]\le j<R[i])$ | + | - $dp[i][j][0]=dp[i-1][j][0]\times 2+(j-L[i])^2,dp[i][j][1]=dp[i-1][j][1]\times 2\ (L[i]\le j<R[i])$ |
| - | - $dp[i][R[i]][0]=dp[i-1][R[i]][0]$ | + | - $dp[i][R[i]][0]=dp[i-1][R[i]][0],dp[i][R[i]][1]=dp[i-1][R[i]][0]+dp[i-1][R[i]][1]\times 2+(R[i]-L[i])^2$ |
| - | - $dp[i][R[i]][1]=dp[i-1][R[i]][0]+dp[i-1][R[i]][1]*2+(R[i]-L[i])^2$ | + | |
| 最后使用线段树或其他数据结构就可以将该$dp$优化到$O(n\log n)$ | 最后使用线段树或其他数据结构就可以将该$dp$优化到$O(n\log n)$ | ||
2020-2021/teams/alchemist/weekly_digest_10.1597398553.txt.gz · 最后更改: 2020/08/14 17:49 由 hardict
