1 条题解

  • 0
    @ 2026-5-3 18:55:28

    bi,jb_{i,j} 表示需要参加第 ii 天的第 jj 场会议的人数,那么就有转移方程(当然 ii 需要从大到小枚举):

    $$b_{i,j}=\sum_{k=1}^{n_{i+1}}[a_{i-1,k}=j]\times b_{i-1,k}$$

    即,每个会议需要的人数就是这个会议的延续会议需要的人数之和。

    那么,如果这个会议没有延续会议,那么此时的 bi,jb_{i,j} 就是 11(需要 11 人参加)。

    答案就是某一天需要的人数之和的最大值。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    int k;
    vector<int>a[500050];
    vector<int>b[500050];
    int c[500500];
    int main(){
        cin>>k;
        int n0;
        cin>>n0;
        c[1]=n0;
        a[1].push_back(-1);//占
        b[1].push_back(0);//位
        for(int i=1;i<=n0;i++) a[1].push_back(0),b[1].push_back(0);
        for(int i=2;i<=k;i++){
            int n;
            cin>>n;
            c[i]=n;
            a[i].push_back(-1);//占
            b[i].push_back(1);//位
            for(int j=0;j<n;j++){
                int x;
                cin>>x;
                a[i].push_back(x);
                b[i].push_back(0);
            }
        }
        int ans=0;
        for(int i=k;i>=1;i--){
            int now=0;
            for(int j=1;j<=c[i];j++){
                if(!b[i][j]) b[i][j]=1;
                if(i!=1) b[i-1][a[i][j]]+=b[i][j];
                now+=b[i][j];
            }
            ans=max(ans,now);
        }
        cout<<ans;
        return 0;
    }
    
    • 1

    信息

    ID
    11492
    时间
    1000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者