o2o家电维修网站开发,网站自己备案,昆山外贸网站建设推广,学完html的收获感受题目链接 选一个派系和一个阵营可以唯一确定一名导师 因为每一个阵营里的导师都分别来自不同派系#xff0c;所以k0时#xff0c;对阵营的选择是不影响对派系的选择的 唯一的限制就是同城市的要在同一个阵营 所以以每个城市为物品#xff0c;物品大小为该城市的人数#xf…题目链接 选一个派系和一个阵营可以唯一确定一名导师 因为每一个阵营里的导师都分别来自不同派系所以k0时对阵营的选择是不影响对派系的选择的 唯一的限制就是同城市的要在同一个阵营 所以以每个城市为物品物品大小为该城市的人数阵营人数为背包容量做背包dp 再以每个学校为物品物品大小为该学校的人数派系人数为背包容量做背包dp 只用一维记录背包大小即可因为总人数-背包里的人数在另一个阵营或派系的人数 然后合并答案即可 方案数是可以相互乘起来的k很小所以我们可以暴力做k0的情况然后乘上符合要求的k0的方案数 k0时记\(f[x][t][i][j]\)为前x个学校前一个学校选择了t阵营此时蓝有i个人鸭派有j个人的方案数 滚动第一维否则空间会爆 将学校按城市排序这样相同城市的就会排在一起转移的时候如果和前一个学校同城就要选择相同阵营 #includebits/stdc.h
#define rep(i,j,k) for(int ij;ik;i)
using namespace std;
typedef long long ll;
typedef double db;
char cch;
inline int rd(){int x0,fl1;cchgetchar();while(cch9||cch0){if(cch-) fl-1;cchgetchar();}while(cch0cch9) x(x3)(x1)cch-0,cchgetchar();return x*fl;
}
const int mod998244353,N3000;
struct abc{int ct,sum,ban;
}p1[N],p2[N];
int f[N],g[N],ff[2][2][N][N],ok[N],bl[N],ct[N],city[N],sum[N],ban[N];
inline void inc(int A,int B){//会比 %mod快一点点 AB;if(Amod) A-mod;if(A0) Amod;
}
inline int mul(int A,int B){return 1ll*A*B%mod;
}
inline int sub(int a,int b){a-b;if(a0) amod;return a;
}
inline int getg(int l,int r){if(lr) return 0;if(l0) return g[r];//为了dp方便g[0]1实际上应该是0return sub(g[r],g[l-1]);
}
inline int getf(int l,int r){if(lr) return 0;if(l0) return f[r];//同理 return sub(f[r],f[l-1]);
}
inline bool cmp(const abc a1,const abc a2){return a1.cta2.ct;
}
inline void sv(){int nrd(),crd(),c0rd(),c1rd(),d0rd(),d1rd(),ans0,tot0;//n所学校c个城市蓝阵营 C0。 红阵营 C1。 鸭派系 D0。 R派系D1。memset(city,0,sizeof city);rep(i,1,n) ct[i]rd(),sum[i]rd(),totsum[i],ban[i]-1,city[ct[i]]sum[i];//city[i]表示第i个城市一共有多少人 int krd(),id;rep(i,1,k) idrd(),ban[id]rd();int len10,len20;rep(i,1,n){if(ban[i]!-1) p1[len1](abc){ct[i],sum[i],ban[i]};//有特殊要求的 else p2[len2](abc){ct[i],sum[i],ban[i]};//没有特殊要求的 }sort(p11,p1len11,cmp);//按城市排序rep(i,1,len1){if(city[p1[i].ct]-1) ok[i]0;//阵营的转移以城市为单位else ok[i]city[p1[i].ct]/*注意*/,city[p1[i].ct]-1;}//memset(g,0,sizeof g),g[0]1;rep(i,1,c) if(city[i]0) for(int jc0;jcity[i];--j) inc(g[j],g[j-city[i]]);/*做前缀和*/rep(i,1,c0) inc(g[i],g[i-1]);//memset(f,0,sizeof f),f[0]1;rep(i,1,len2) for(int jd0;jp2[i].sum;--j) inc(f[j],f[j-p2[i].sum]);/*做前缀和*/rep(i,1,d0) inc(f[i],f[i-1]);//memset(ff,0,sizeof ff);//ff[x][t][i][j]为前x个学校前一个学校选择了t阵营此时蓝有i个人鸭派有j个人的方案数滚动第一维 ff[0][0][0][0]1;int cnt0,now0;rep(i,1,len1){//对有要求的学校暴力求解now^1;int tmpp1[i].sum,bnp1[i].ban,dok[i],lstcnt;//lst之前的学校的总人数 cnttmp;rep(t,0,1) rep(h,0,c0) rep(j,0,cnt) ff[now][t][h][j]0;//这里不可以用memset用了会超时因为一开始cnt很小所以循环更快 rep(t,0,1){int cs-1;//choiseif(i1p1[i].ctp1[i-1].ct) cst; for(int ic0;i0;--i) for(int jcnt;j0;--j){if(cs!1){//如果同城市的选择了0阵营或与上一个不同城if(bn!1idjlst) inc(ff[now][0][i][j],ff[now^1][t]/*注意是t而不是0*/[i-d][j]);//没有禁掉小R可以加入R派 if(bn!0idj-tmplstjtmp) inc(ff[now][0][i][j],ff[now^1][t][i-d][j-tmp]);//没有禁掉Yazid可以加入鸭派}if(cs!0){//如果同城市的选择了1阵营或与上一个不同城if(bn!3jlst) inc(ff[now][1][i][j],ff[now^1][t][i][j]);if(bn!2j-tmplstjtmp) inc(ff[now][1][i][j],ff[now^1][t][i][j-tmp]);}}}}//rep(t,0,1) rep(i,0,c0) rep(j,0,d0){int vff[now][t][i][j];if(!v)continue;int t1c0-i,t2max(0,tot-d1-j),t3max(0,tot-c1-i),t4d0-j;//符合人数要求的区间 inc(ans,mul(v,mul(getg(t3,t1),getf(t2,t4))));}printf(%d\n,ans);
}
int main(){int Trd();while(T--) sv();
}
/*
2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1
*/ 转载于:https://www.cnblogs.com/Doingdong/p/10727364.html
