[ARC164E] Segment-Tree Optimization 题解

题目链接

题目链接

题目解法

一个自认为比较自然的解法

这种一段序列切成两部分的问题首先考虑区间 \(dp\)
令 \(f_{l,r}\) 为 \([l,r]\) 能构成的最小深度，\(g_{l,r}\) 为在 \(f_{l,r}\) 最小的情况下最少的最大深度的点的个数
转移枚举 \(k\) 即可
需要在下面是叶子的时候处理一些边界问题
这样复杂度是 \(O(n^3)\) 的

套路的，我们试一试用四边形不等式，发现能过，但我也不知道怎么证决策单调性
时间复杂度 \(O(n^2)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=4100,inf=1e9;
struct Node{ int f,g;}dp[N][N];
bool chk(Node o1,Node o2){
    if(o1.f^o2.f) return o1.f<o2.f;
    return o1.g<o2.g;
}
int n,m,s[N][N],pos[N][N];
int calc(int x1,int x2,int y1,int y2){ return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];}
int main(){
    read(n),read(m);
    F(i,1,m){ int l,r;read(l),read(r);s[l][r]++;}
    if(s[1][n]==m){ printf("0 %d\n",m);exit(0);}
    F(i,1,n) F(j,1,n) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    F(i,1,n) dp[i][i]={0,0},pos[i][i]=i;
    F(len,2,n) F(l,1,n-len+1){
        int r=l+len-1;
        int res=calc(1,l-1,1,l-1)+calc(r+1,n,r+1,n)+calc(1,l,r,n);
        if(res==m){ dp[l][r]={0,0},pos[l][r]=l;continue;}
        dp[l][r]={inf,inf},pos[l][r]=l;
        F(k,pos[l][r-1],min(r-1,pos[l+1][r])){
            auto dp1=dp[l][k],dp2=dp[k+1][r];
            Node ndp;
            if(!dp1.f&&!dp2.f) ndp.f=1,ndp.g=calc(1,l,l,r-1)+calc(1,l,l,k)+calc(k+1,r,r,n)+calc(l+1,r,r,n);
            else{
                if(dp1.f>dp2.f) ndp=dp1,ndp.f++;
                else if(dp1.f<dp2.f) ndp=dp2,ndp.f++;
                else ndp={dp1.f+1,dp1.g+dp2.g};
            }
            if(chk(ndp,dp[l][r])) dp[l][r]=ndp,pos[l][r]=k;
        }
    }
    printf("%d %d\n",dp[1][n].f,dp[1][n].g);
    return 0;
}