2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛85
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛85 [2021/06/29 11:23] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛85 [2021/06/29 17:04] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 牛客练习赛83 ====== | + | ====== 牛客练习赛85 ====== |
| - | [[https://ac.nowcoder.com/acm/contest/11173|比赛链接]] | + | [[https://ac.nowcoder.com/acm/contest/11175|比赛链接]] |
| ===== F - 音游家的谱面(Hard version) ===== | ===== F - 音游家的谱面(Hard version) ===== | ||
| 行 22: | 行 22: | ||
| $$ | $$ | ||
| - | f(i,j)=\min\left(f(i-1,k)+\min(\max(|p_i-p_{i-1}|,|j-k|),\max(|p_i-k|,|j-p_{i-1}|))\right) | + | f(i,j)\gets f(i-1,k)+|p_i-p_{i-1}|(|j-k|\le |p_i-p_{i-1}|) |
| + | $$ | ||
| + | |||
| + | $$ | ||
| + | f(i,j)\gets f(i-1,k)+|p_i-k|(|j-p_{i-1}|\le |p_i-k|) | ||
| $$ | $$ | ||
| 暴力做法时间复杂度 $O(n^2m)$，方案输出用回溯即可。 | 暴力做法时间复杂度 $O(n^2m)$，方案输出用回溯即可。 | ||
| - | 考虑两棵线段树维护序列 $\{f(i-1,k)+\max(|p_i-p_{i-1}|,|j-k|)\}$ 和 $\{f(i-1,k)+\max(|p_i-k|,|j-p_{i-1}|)\}$ 的最小值。 | + | 考虑线段树优化，枚举 $k$ 然后更新特定范围的 $f(i,j)$。线段树只需要维护区间最值操作和单点查询操作，时间复杂度 $O(nm\log n)$。 |
| - | $j\to j+1$，不难发现对上述两个序列都可以通过分类讨论后用区间加操作维护，于是时间复杂度 $O(nm\log n)$。 | + | 该复杂度实际上已经可能可以通过本题(如果卡常技巧优秀)，但实际上存在进一步优化。 |
| + | 不难看出第一种转移式可以用单调队列优化。 | ||
| + | 第二种转移式预处理出 $t=0\sim n-1$ 时 $\min(f(i-1,k)+|p_i-k|(t\le |p_i-k|))$ 的结果，然后枚举 $j$ 然后根据 $|j-p_{i-1}|$ 直接查询即可。 | ||
| + | |||
| + | 时间复杂度优化为 $O(nm)$。 | ||
| + | |||
| + | 教训：本人一开始想出的转移式如下所示。 | ||
| + | |||
| + | $$ | ||
| + | f(i,j)= \min(f(i-1,k)+\min(\max(|p_i-p_{i-1}|,|j-k|),\max(|p_i-k|,|j-p_{i-1}|))) | ||
| + | $$ | ||
| + | |||
| + | 只能用线段树做到 $O(nm\log n)$，实现复杂且没法进一步优化，以后应该在填表法比较复杂时考虑刷表法。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| + | const int MAXN=5005,inf=1e9; | ||
| + | int dp[MAXN][MAXN],pre[MAXN][MAXN],p[MAXN],res[MAXN]; | ||
| + | pair<int,int> que[MAXN],temp[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,m)p[i]=read_int(); | ||
| + | _rep(i,0,m)_rep(j,1,n)dp[i][j]=inf; | ||
| + | p[0]=1; | ||
| + | dp[0][n]=0; | ||
| + | _rep(i,1,m){ | ||
| + | int head=0,tail=1,lim=abs(p[i]-p[i-1]); | ||
| + | _rep(j,1,lim){ | ||
| + | while(head>=tail&&que[head].first>=dp[i-1][j])head--; | ||
| + | que[++head]=make_pair(dp[i-1][j],j); | ||
| + | } | ||
| + | _rep(j,1,n){ | ||
| + | if(j+lim<=n){ | ||
| + | while(head>=tail&&que[head].first>=dp[i-1][j+lim])head--; | ||
| + | que[++head]=make_pair(dp[i-1][j+lim],j+lim); | ||
| + | } | ||
| + | if(head>=tail&&que[tail].second+lim<j)tail++; | ||
| + | dp[i][j]=que[tail].first+lim; | ||
| + | pre[i][j]=que[tail].second; | ||
| + | } | ||
| + | temp[n]=make_pair(inf,0); | ||
| + | for(int lim=n-1;lim>=0;lim--){ | ||
| + | int lpos=p[i]-lim,rpos=p[i]+lim; | ||
| + | temp[lim]=temp[lim+1]; | ||
| + | if(lpos>=1) | ||
| + | temp[lim]=min(temp[lim],make_pair(dp[i-1][lpos]+abs(p[i]-lpos),lpos)); | ||
| + | if(rpos<=n) | ||
| + | temp[lim]=min(temp[lim],make_pair(dp[i-1][rpos]+abs(p[i]-rpos),rpos)); | ||
| + | } | ||
| + | _rep(j,1,n){ | ||
| + | int lim=abs(j-p[i-1]); | ||
| + | if(dp[i][j]>temp[lim].first){ | ||
| + | dp[i][j]=temp[lim].first; | ||
| + | pre[i][j]=temp[lim].second; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int ans=inf; | ||
| + | _rep(i,1,n) | ||
| + | ans=min(ans,dp[m][i]); | ||
| + | _rep(i,1,n){ | ||
| + | if(ans==dp[m][i]){ | ||
| + | int pos=i; | ||
| + | for(int j=m;j;j--){ | ||
| + | res[j]=dp[j][pos]; | ||
| + | pos=pre[j][pos]; | ||
| + | } | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | _rep(i,1,m) | ||
| + | space(res[i]); | ||
| + | return 0; | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛85.1624937032.txt.gz · 最后更改: 2021/06/29 11:23 由 jxm2001
