1 条题解
-
0
令 表示需要参加第 天的第 场会议的人数,那么就有转移方程(当然 需要从大到小枚举):
$$b_{i,j}=\sum_{k=1}^{n_{i+1}}[a_{i-1,k}=j]\times b_{i-1,k}$$即,每个会议需要的人数就是这个会议的延续会议需要的人数之和。
那么,如果这个会议没有延续会议,那么此时的 就是 (需要 人参加)。
答案就是某一天需要的人数之和的最大值。
代码:
#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
- 上传者