1 条题解

  • 0
    @ 2024-6-4 18:20:37

    暴力部分

    除了n10n\leq 10的部分分以外,其他部分都需要多多少少用到正解。

    n10n\leq 10的时候,我们可以大力爆搜划分的方式,具体策略可以是:我一开始用nn个单点的区间,然后每次枚举相邻的两个区间,把他们合并成一个区间,然后继续搜索下去,直到他们合成[1,n][1,n]为止。

    总的方案数显然可以用一个dpdp来计算:dpn=dpldpn1ldp_n=\sum dp_l dp_{n-1-l},典型的卡特兰数。

    搜完以后就可以直接枚举每个区间去计算答案了。

    正解

    我们考虑这样一件事:fl,rf_{l,r}的下界是11,这是显然的。

    什么时候会让fl,rf_{l,r}增加呢?

    当且仅当,当前线段树上有一个区间[L,R][L,R],这个区间[L,R][L,R][l,r][l,r]有交集,但是又不是包含关系(这样说明你一定会在查询的时候进入[L,R][L,R]这个节点);你从k(Lk<R)k(L\leq k<R)处把这个区间划分开了,而kk满足lk<rl\leq k<r

    这时候,你必定会递归[L,R][L,R]的两边子树,那每个子树至少会产生一个代价,答案的下界就增加了11

    所以结论是,在你查询的过程中,“双边递归”的次数就是查询到的区间个数了。

    所以我们就可以按照线段树上节点被“双边递归”的次数来dp了。

    dpl,rdp_{l,r}表示当前线段树上的区间是[l,r][l,r],你把它划分完毕后,内部被双边递归的最小总次数。

    $dp_{l,r}=\min_{k=l}^{r-1}(dp_{l,k}+dp_{k+1,r}+cost(l,r,k))$。

    cost(l,r,k)cost(l,r,k)指的是,有多少个查询的区间,和[l,r][l,r]有交集,但不是包含关系,且经过了位置k+0.5k+0.5

    这个可以被简化成:有多少个查询的区间,经过了[k+0.5][k+0.5],且跟[l,r][l,r]不是包含关系。

    我们可以预处理w[k]w[k]表示有多少个区间经过了k+0.5k+0.5这个位置。

    预处理num[l][r]num[l][r]表示有多少个查询的区间包含了[l,r][l,r]

    然后用w[k]num[l][r]w[k]-num[l][r]来代表答案。

    num[l][r]num[l][r]可以用类似二维前缀和的思路来做,包含了[l,r][l,r]的区间个数,等于包含了[l1,r],[l,r+1][l-1,r],[l,r+1]的区间个数,减去包含了[l1,r+1][l-1,r+1]的区间个数,再加上区间[l,r][l,r]的个数。按区间大小从大到小做即可。

    最后的时间复杂度:O(n3)O(n^3)

    #include<bits/stdc++.h>
    #define ll long long
    #define maxn 505
    using namespace std;
    int n,Q;
    int w[maxn]; //经过[i+0.5]这个位置的区间有多少个 
    int num[maxn][maxn]; //包含这个区间的区间有多少个 
    int l,r; 
    ll dp[maxn][maxn];
    int main()
    {
    	cin>>n>>Q;
    	for (int i=1;i<=Q;i++)
    	{
    		cin>>l>>r; num[l][r]++;
    		w[l]++; w[r]--;
    	}
    	for (int i=1;i<=n;i++) w[i]+=w[i-1];
    	for (int len=n-1;len>=1;len--)
    	for (int l=1;l+len-1<=n;l++)
    	{
    		int r=l+len-1;
    		num[l][r]=num[l][r]+num[l-1][r]+num[l][r+1]-num[l-1][r+1];
    	}
    	
    	for (int len=2;len<=n;len++)
    	for (int l=1;l+len-1<=n;l++)
    	{
    		int r=l+len-1;
    		dp[l][r]=1ll<<60;
    		for (int k=l;k<r;k++)
    		{
    			dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+(w[k]-num[l][r]));
    		}	
    	}
    	cout<<dp[1][n]+Q<<endl;
    }
    
    • 1

    信息

    ID
    1421
    时间
    2000ms
    内存
    512MiB
    难度
    5
    标签
    (无)
    递交数
    33
    已通过
    15
    上传者