BZOJ5123 线段树的匹配（树形dp）

　　线段树的任意一棵子树都相当于节点数与该子树相同的线段树。于是假装在树形dp即可，记忆化搜索实现，有效状态数是logn级别的。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

ll n;

map<ll,ll> f[],g[];

void solve(ll n)

{

    if (g[].find(n)!=g[].end()) return;

    ll lson=n+>>,rson=n-lson;

    solve(lson),solve(rson);

    f[][n]=max(f[][lson],f[][lson])+max(f[][rson],f[][rson]);

    f[][n]=max(f[][lson]+max(f[][rson],f[][rson]),f[][rson]+max(f[][lson],f[][lson]))+;

    ll x=f[][lson]==f[][lson]?g[][lson]+g[][lson]:(f[][lson]>f[][lson]?g[][lson]:g[][lson]);

    ll y=f[][rson]==f[][rson]?g[][rson]+g[][rson]:(f[][rson]>f[][rson]?g[][rson]:g[][rson]);

    g[][n]=x*y%P;

    if (f[][lson]+max(f[][rson],f[][rson])==f[][rson]+max(f[][lson],f[][lson]))

    g[][n]=(g[][lson]*y+x*g[][rson])%P;

    else if (f[][lson]+max(f[][rson],f[][rson])>f[][rson]+max(f[][lson],f[][lson])) g[][n]=g[][lson]*y%P;

    else g[][n]=x*g[][rson]%P;

    return;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5123.in","r",stdin);

    freopen("bzoj5123.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    cin>>n;f[][]=,f[][]=-n,g[][]=,g[][]=;

    solve(n);

    if (f[][n]==f[][n]) cout<<f[][n]<<' '<<(g[][n]+g[][n])%P;

    else if (f[][n]>f[][n]) cout<<f[][n]<<' '<<g[][n];

    else cout<<f[][n]<<' '<<g[][n];

    return ;

}

秒客网

BZOJ5123 线段树的匹配（树形dp）

相关文章