题解：P11761 [IAMOI R1] 明码标价

· · 题解

中位数二分来的实惠。

考虑小于等于 mid 的记作 -1，否则记作 1，我们查看此时中位数是否是 -1，容易证明单调性。

这有个很好的性质，就是一个这样的序列 -1 是中位数，当且仅当序列和小于等于 0。

考虑 dp。

设 dp_{i,c} 表示在 i 的前缀中，每一段的中位数的和等于 c 的方案数。

转移考虑枚举 j，表示最后一段的第一个数的下标，然后计算这一段中位数，然后把 dp_{j-1,-n\sim n} 直接拿过来转移就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[109];
int b[109];
int n;
__int128 dp[109][209];//第二维都多加了 100，这里的 dp[i][j] 表示实际上的 dp[i][j-100}
int check(){
    dp[0][100]=1;
    for(int i=1;i<=n;i++){
        int sum;
        sum=b[i];
        for(int c=0;c<=200;c++){
            dp[i][c]=0;
        }
        for(int j=i-1;j>=0;j--){
            if(sum<=0){
                for(int c=0;c<=200;c++){
                    dp[i][c]+=dp[j][c+1];
                }
            }else{
                for(int c=1;c<=200;c++){
                    dp[i][c]+=dp[j][c-1];
                }
            }
            sum+=b[j];
        }
    }
    __int128 ans;
    ans=0;
    for(int i=0;i<=200;i++){
        ans+=dp[n][i]*(i<=100?-1:1);

    }
    return (ans<=0?-1:1);
}
signed main(){
    std::ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l,r;
    l=1,r=1000000000;
    while(l<r){
        int mid;
        mid=l+r;
        mid>>=1;
        for(int i=1;i<=n;i++){
            b[i]=(a[i]<=mid?-1:1);
        }
        if(check()==-1){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<l;
    return 0;
}

更优解

注意到这个解法的性质过于优秀，我们尝试冲击平方。

回想一下我们 DP 有哪些比较普通的优化方法。

其中一个就是拿之前做的省掉一部分工序。

什么意思？就是转移可能有重复的，我们不想重复做。

我们试试？

注意到计数器 sum 变为 0 时似乎情况出现了些许不同。

此时继续下去与此时的 dp_{j,-c\sim c} 转移的时候是一致的。

我们可以直接省掉，把 dp_{j,-c\sim c} 的成果直接拿过来。

当然别忘了特判 j=0，这时候的转移可不太一样。

添加这条语句。

if(sum==0&&j){
  for(int c=0;c<=200;c++){
    dp[i][c]+=dp[j][c];
  }
  break;
}

虽然复杂度没变，但是代码却有了下限，如果 1 和 -1 随机生成，效果会非常好。

事实上我们增加这段后时间从 80 毫秒来到了 69 毫秒，可以说确实有了进步。

我们继续探索，我们发现如果计数器 sum 变成了 0，在此之前其正负性一定不变，因为之前每次就加一或者减一，然后就判定，来不及改变。

而对于正负性相同的 sum，我们转移是一样的啊！

所以可以直接前缀和优化这部分。

至于判断是正的还是负的，我们看 sum 最开始的值即可。

不过还有个难点就是如何确定在哪个位置 sum 最早取到 0。

我们考虑 i 移动时，每次会让每个 sum 都增加一个数，我们转换成 sum 没加就是目标从 0 转换成了另一个数。

具体的，我们维护 jj_i 表示增加的数的前缀和为 i 的最大的 j。

为啥是前缀和？这个好维护。

然后在增加一个数增加多少，指针就增加多少。

然后算上自己就行。

如下所示，第一个是维护指针，第二个算自己的语句，实际写的时候二者并不会写在一起。

当然，细节较多，别忘了 sum 可能取不到 0。

zz+=b[i];//zz 表示指针
jj[zz]=i;

然后我们就得到了一个复杂度 O(n^2\log n) 的算法。

#include<bits/stdc++.h>
using namespace std;
int a[109];
int b[109];
int n;
__int128 dp[109][209];
__int128 qz[109][209];
int jj[209];
int zz;
int check(){
    dp[0][100]=1;
    for(int i=0;i<=200;i++){
        jj[i]=-1;//sum 取不到 0 的情况认为是 -1
    }
    jj[100]=0;
    zz=100;
    qz[0][100]=1;
    for(int i=1;i<=n;i++){
        zz+=b[i];
        for(int c=0;c<=200;c++){
            dp[i][c]=0;
        }
        if(jj[zz]==-1){
            if(b[i]<=0){
                for(int c=0;c<=200;c++){
                    dp[i][c]+=qz[i-1][c+1];
                }
            }else{
                for(int c=1;c<=200;c++){
                    dp[i][c]+=qz[i-1][c-1];
                }
            }
        }else{
            if(b[i]<=0){
                for(int c=0;c<=200;c++){
                    dp[i][c]+=qz[i-1][c+1]-qz[jj[zz]][c+1];
                }
            }else{
                for(int c=1;c<=200;c++){
                    dp[i][c]+=qz[i-1][c-1]-qz[jj[zz]][c-1];
                }
            }
            for(int c=0;c<=200;c++){
                dp[i][c]+=dp[jj[zz]][c+1];
            }
            if(jj[zz]){
                for(int c=0;c<=200;c++){
                    dp[i][c]+=dp[jj[zz]][c];
                }
            }
        }
        jj[zz]=i;
        for(int c=0;c<=200;c++){
            qz[i][c]=dp[i][c]+qz[i-1][c];
        }
    }
    __int128 ans;
    ans=0;
    for(int i=0;i<=200;i++){
        ans+=dp[n][i]*(i<=100?-1:1);

    }
    return (ans<=0?-1:1);
}
signed main(){
    std::ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l,r;
    l=1,r=1000000000;
    while(l<r){
        int mid;
        mid=l+r;
        mid>>=1;
        for(int i=1;i<=n;i++){
            b[i]=(a[i]<=mid?-1:1);
        }
        if(check()==-1){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<l;
    return 0;
}

这样我们的代码虽然常数很大，但是复杂度在那里，所以只需要跑 20 毫秒，可以进入最优解第一页。

但是这道题还是受到整数类型影响，导致 n 最大开到 100，挺可惜的。