主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解 P3592 【[POI2015]MYJ】
最后更新于 2025-08-28 13:40:20
作者
JohnJoeZhu
分类
题解
题解
P3592
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
[题面传送门](https://www.luogu.com.cn/problem/P3592) ## 1.寻找算法方向 ##### 1.1 数据范围 首先我们发现，n竟然只有50！ 说明我们肯定是要多次枚举位置的 时间复杂度估计在$O(n^2m)$至$O(n^3m)$之间 ##### 1.2 初步暴力 暴力的目的是求出在解题过程中我们大致需要枚举的量 首先我们可以枚举每个点的取值，然后统计有效区间 实际大致可以做到$O(n\space max(c))$ ##### 1.3 明确算法 暴力不好写，而从暴力得到的复杂度低于上限，那是否说明我们可以通过$O(n)$至$O(n^2)$的枚举来快速得到答案 可是我们发现每个人的要求是区间性的，那么我们是不是可以对每个区间单独考虑，然后再合并 这个思想，不就是**区间dp**吗？（当然你也可以感性理解，大胆猜想qwq） ## 2.完善dp步骤 既然是dp了，那就肯定要走dp那几步的 ##### 2.1 设计状态 常规设计是$f[i][j]$表示区间$[i,j]$的收益最大值 由于我们暴力发现需要枚举最小值的位置（即断点）和最小值，所以我们应该这样子设计 $f[i][j][k]$表示区间$[i,j]$，最小值为$k$的最大收益 ##### 2.2 确定转移方程 由于我们要枚举最小值的位置（即断点），那就可以这样子写 $f[i][j][k]=max(f[i][l-1][k]+f[l+1][j][k]+val(i,j,l,k))(i<=l<=j)$ $val(i,j,l,k)$表示在区间$[i,j]$内的顾客，当最小值在$l$处，最小值为$k$的价值 $val(i,j,l,k)=cnt(i,j,l,k)*k$ $cnt(i,j,l,k)$也就是在区间$[i,j]$内的顾客，当最小值在$l$处，最小值为$k$时，在$l$处消费的顾客数量 如果我们稍加思考，我们应该发现我们取值后的结果是可传递的 也就是说，$f[i][j][k]=max(f[i][j][k],f[i][j][k+1])$ 因为我们选择k为最小值，k+1也是可以选的，顾客少了可是每个人交的钱多了 所以应该有两个方程 $$ f[i][j][k]=max\left\{ \begin{aligned} f[i][j][k+1]\\ max(f[i][l-1][k]+f[l+1][j][k]+val(i,j,l,k))(i<=l<=j)\\ \end{aligned} \right. $$ ##### 2.3 得到答案 显然，答案应该是$f[1][n][k]$ 那么k应该是多少呢？ 我们现在知道，k=1时已经把其他的k的答案都传递了，所以k就是1啦 那么方案呢？（注意有SPJ） 常规操作，我们在枚举过程中记录下断点即最优决策点，再**记录下最优取值k** 这里要注意后者是指向第二个方程的，也就是说，最小值为k，它的最优取值不一定为k 然后就递归求解，直接输出 ##### 2.4 优化算法 咦？解决什么问题呢？ 我们分析一下时间复杂度 枚举区间状态$O(n^2\space max(c_i))$ 枚举断点$O(n)$ 转移方程（即求val/cnt）$O(m)$ 那复杂度就是$O(n^3m\space max(c_i))$ 显然我们可以优化 首先，我们发现求val应该是可以优化的 因为对于一个区间，在某一位置取某一固定值，顾客数是不变的 那么就是说，我们可以**预处理cnt**，复杂度$O(m\space max(c_i))$ 然后我们就看到了一直没有处理的$O(max(c_i))$ 这是一个题目没有给出的值（似乎是$5e5$由于某些原因不见了） 显然我们是不可以使用它的 但是我们真的需要从$1-max(c_i)$枚举吗？ 如果我们可以取$c_i$和$c_j(c_i>c_j)$，只有在两个临界点才会产生贡献 也就是说，当我们取$(c_j,c_i)$中的值时，既不能够增加顾客数量，又不能够增大收入（本来的$c_i$的收入越来越小了） 所以我们得到每一个店的标价，只有在某一个$c_i$取值才会最优 那就**离散化**！ 我们再来计算时间复杂度 枚举区间状态$O(n^2m)$ 枚举断点$O(n)$ 求cnt（这里应该好理解），此时不需要嵌套 $O(nm)$ 这里外层有一个$O(n^2)$的枚举区间 所以总复杂度应该是$O(n^3m)$ ## 3. 代码实现 相信来到紫题的大佬都很牛逼，所以这里只给出部分代码 ##### 3.1 离散化 这就太容易了吧 ##### 3.2 对于每个区间求出cnt ```cpp for(int len=1;len<=n;len++) for(int i=1,j=i+len-1;j<=n;i++,j=i+len-1)//枚举区间 { for(int k=i;k<=j;k++) for(int l=1;l<=tot;l++)//tot为离散化后实际有多少个不同的c g[k][l]=0;//因为重复，所以要清零，这里是cnt for(int k=1;k<=m;k++) if(a[k]>=i&&j>=b[k])//注意顾客区间必须在枚举的区间内，否则顾客可能在其他区间内消费 for(int l=a[k];l<=b[k];l++) g[l][c[k]]++; for(int k=i;k<=j;k++) for(int l=tot-1;l;l--)//如果l可以，那么比l小的都可以 g[k][l]+=g[k][l+1];//求出每个点，每个价值可以收获的顾客 } ``` ##### 3.3 转移方程 ```cpp for(int len=1;len<=n;len++) for(int i=1,j=i+len-1;j<=n;i++,j=i+len-1) for(int k=tot;k;k--)//枚举最小值 { int anss=0,sum; for(int l=i;l<=j;l++)//枚举断点 if((sum=f[i][l-1][k]+f[l+1][j][k]+g[l][k]*d[k])>=anss) anss=sum,num[i][j][k]=l;//转移方程显然,num存决策点 if(anss>=f[i][j][k+1]) f[i][j][k]=anss,val[i][j][k]=k;//与k+1比较（由于不同情况需要更新的内容不同 ，val为最优值 else f[i][j][k]=f[i][j][k+1],val[i][j][k]=val[i][j][k+1]; } ``` ##### 3.4 求出答案 ```cpp void gans(int l,int r,int k) { if(l>r) return; int point=num[l][r][k=val[l][r][k]];//得到决策点，注意这里的k不一定是原来的k，应该是最优的k ans[point]=d[k];//答案函数 gans(l,point-1,k),gans(point+1,r,k);//递归求解 } ``` 然后完整代码就不给出了 然后就没有然后了 **完结撒花** [顺手广告](https://www.luogu.com.cn/blog/JohnJoeZHU/#type=%E9%A2%98%E8%A7%A3)
正在渲染内容...
点赞
49
收藏
0
