题解 P3592 【[POI2015]MYJ】

JohnJoeZhu · 2020-08-05 09:29:21 · 题解

题面传送门

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]的收益最大值

由于我们暴力发现需要枚举最小值的位置（即断点）和最小值，所以我们应该这样子设计

因为我们选择k为最小值，k+1也是可以选的，顾客少了可是每个人交的钱多了

所以应该有两个方程

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

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 转移方程

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 求出答案

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);//递归求解
}

然后完整代码就不给出了

然后就没有然后了

完结撒花

顺手广告