第负一题

分治+DP

只会 $ n^2 $ 暴力.

$dpl[i][0/1] 向左选/不选 mid 的最大值$

$dpr[i][0/1] 向右选/不选 mid 的最大值$

$ ans = \sum _{i=l} ^{mid} \sum _{j=mid+1} ^{r} max( dpl[i][0]+dpr[j][0],dpl[i][1]+dpr[j][0],dpr[i][0]+dpr[j][1] ) ,但这个形式并不好处理.$

$ 可以转化为 ans = \sum _{i=l} ^{mid} \sum _{j=mid+1} ^{r} max(dpl[i][1]-dpl[i][0],dpr[j][1]-dpr[j][0],0) +dpl[i][0]+dpr[j][0] (直接拆出去加减就好) 发现依旧不好处理 $

$ 设 fl[i] = max _{i=l}^{mid} (dpl[i][1]-dp[i][0],0)，fr[i] =max _{i=mid+1}^{r} (dpr[i][1]-dpr[i][0],0) $

$ ans = \sum _{i=l} ^{mid} \sum _{j=mid+1} ^{r} max(fl[i],fr[j])+dpl[i][0]+dpr[j][0] $

分治很妙,把$i,j$分开并各自统一的转化很妙也很关键.

Code

#include<cstdio>
#include<algorithm>
#include<cstring>

#define int long long
using namespace std;
const int N=2e5+5;
const int mod=998244353;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline int max(int a,int b){
    return a>b?a:b;
}

int n;
int a[N];
int ans;
int dp[N][2];
int dpl[N][2],dpr[N][2];
int fl[N],fr[N];

void work1(int l,int r,int mid){
    dp[mid][0]=0,dp[mid][1]=-mod;
    for(int i=mid-1;i>=l;i--){
        dp[i][0]=max(dp[i+1][1],dp[i+1][0]);
        dp[i][1]=dp[i+1][0]+a[i];
        dpl[i][0]=max(dp[i][0],dp[i][1]);
    }

    dp[mid][0]=-mod,dp[mid][1]=a[mid];
    for(int i=mid-1;i>=l;i--){
        dp[i][0]=max(dp[i+1][1],dp[i+1][0]);
        dp[i][1]=dp[i+1][0]+a[i];
        dpl[i][1]=max(dp[i][0],dp[i][1]);
    }

    dp[mid+1][0]=0,dp[mid+1][1]=-mod;
    for(int i=mid+2;i<=r;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+a[i];
        dpr[i][0]=max(dp[i][0],dp[i][1]);
    }
    
    dp[mid+1][0]=-mod,dp[mid+1][1]=a[mid+1];
    for(int i=mid+2;i<=r;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+a[i];
        dpr[i][1]=max(dp[i][0],dp[i][1]);
    }

    dpl[mid][0]=dpr[mid+1][0]=0;
    dpl[mid][1]=a[mid],dpr[mid+1][1]=a[mid+1];
}

void work2(int l,int r,int mid){
    for(int i=l;i<=mid;i++){
        fl[i]=max(dpl[i][1]-dpl[i][0],0);
        ans=(ans+(r-mid)*dpl[i][0]%mod)%mod;
    }
    for(int i=mid+1;i<=r;i++){
        fr[i]=max(dpr[i][1]-dpr[i][0],0);
        ans=(ans+(mid-l+1)*dpr[i][0]%mod)%mod;
    }

    sort(fl+l,fl+mid+1);
    sort(fr+mid+1,fr+r+1);

    int ql=l,qr=mid+1;

    while(ql<=mid){
        while(qr<=r&&fr[qr]<=fl[ql]){
            ans=(ans+fr[qr]*(ql-l)%mod)%mod;
            ++qr;
        }
        ans=(ans+fl[ql]*(qr-mid-1)%mod)%mod;
        ++ql;
    }
    while(qr<=r){
        ans=(ans+fr[qr]*(mid-l+1)%mod)%mod;
        ++qr;
    }
}

void solve(int l,int r){
    if(l==r){
        ans=(ans+a[l])%mod;
        return ;
    }

    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);

    work1(l,r,mid);
    work2(l,r,mid);
}

signed main(){
    n=read();

    for(int i=1;i<=n;i++)
        a[i]=read();
    
    solve(1,n);
    
    printf("%lld ",ans%mod);
    
    return 0;
}

数树

暴力只会枚举排列,链和外向树都不会

正解是容斥+树上背包

直接求限制太多,我们求非法的方案数$ sum _i $ 总方案 $ (n-i)!sum_i $ 容斥系数由二项式反演得出.只是系数不一样.

$ 设 dp[i][j][0/1/2/3] 表示节点 i ，选了 j 条边 0:独立节点,1:有入边,2:有出边,3:既有入边又有出边. sum_i = \sum _{k=0}^{3} dp[1][i][k] $

树上背包就好,一个合并子树的过程.

Code

#include<cstdio>
#include<cstring>

using namespace std;
const int N=5005;
const int mod=998244353;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct Node{
    int to,next,typ;
}e[N<<1];
int lk[N],ntot;

void add(int x,int y,int typ){
    e[++ntot]=(Node){y,lk[x],typ};
    lk[x]=ntot;
}

int n;
int fac[N];
int siz[N];
int dp[N][N][4],dp1[N][4];

void work(int x,int y,int typ){
    memset(dp1,0,sizeof(dp1));
    for(int i=0;i<=siz[x]-1;i++){
        for(int j=0;j<=siz[y]-1;j++){
            int sum=0;

            for(int k=0;k<=3;k++)
                sum=(sum+dp[y][j][k])%mod;
            for(int k=0;k<=3;k++)
                dp1[i+j][k]=(dp1[i+j][k]+1ll*sum*dp[x][i][k]%mod)%mod;
            
            if(typ==0){
                dp1[i+j+1][1]=(dp1[i+j+1][1]+1ll*dp[x][i][0]*(dp[y][j][0]+dp[y][j][1])%mod)%mod;
                dp1[i+j+1][3]=(dp1[i+j+1][3]+1ll*dp[x][i][2]*(dp[y][j][0]+dp[y][j][1])%mod)%mod;
            }else{
                dp1[i+j+1][2]=(dp1[i+j+1][2]+1ll*dp[x][i][0]*(dp[y][j][0]+dp[y][j][2])%mod)%mod;
                dp1[i+j+1][3]=(dp1[i+j+1][3]+1ll*dp[x][i][1]*(dp[y][j][0]+dp[y][j][2])%mod)%mod;
            }
        }
    }

    siz[x]+=siz[y];

    for(int i=0;i<=siz[x];i++){
        for(int k=0;k<=3;k++){
            dp[x][i][k]=dp1[i][k];
        }
    }
}

void dfs(int x,int fa){
    siz[x]=1;
    dp[x][0][0]=1;

    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;
        
        if(y==fa)
            continue;
        dfs(y,x);
        work(x,y,e[i].typ);
    }
}

int main(){
    // freopen("in","r",stdin);

    n=read();

    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        add(x,y,1),add(y,x,0);
    }

    fac[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
    }

    dfs(1,0);
    
    int ans=0;
    
    for(int i=0,opt=1;i<=n-1;i++,opt=-opt){
        int sum=0;

        for(int k=0;k<=3;k++)
            sum=(sum+dp[1][i][k])%mod;
        ans=(ans+1ll*opt*fac[n-i]*sum%mod+mod)%mod;
    }

    printf("%d ",ans);

    return 0;
}

石子游戏

考场 $ n^2 $ 都没手完出来……

dp挺冷门的.

题解

子段和

暴力不会,正解不会.

标签：ch,14,int,mid,模拟,dpl,CSP,dp,dpr
From： https://www.cnblogs.com/yszy/p/17609882.html

CSP模拟14

第负一题

数树

石子游戏

子段和

相关文章

赞助商

阅读排行