Antinomy之命运的抉择

XCPC宇宙中的大学僧们在大学毕业的时候，主要会有两个职业方向，科研 or 开发。这个选择是因僧而异的。对于一个这一届XCPC宇宙的大学僧来说，其有以下三个属性：

开发兴趣加成： $\mathit b$
科研兴趣加成： $\mathit c$
其大学期间总共拥有的学习时间： $totalTime$

每一个大学僧在XCPC宇宙的大学中进修的时候，有机会去选择去学习或不学习 $\mathit n$ 个学习节点。

其中学习节点可以分为两个组：开发、科研。对于每一个组，其中有若干个子类型。对于每一个子类型，有如下三个属性：

最多学习该子类型次数： $amount_i$
每一次学习该子类型需要花费： $cost_i$
每一次学习该子类型带来的所属类型的能力值的提升： $a_i$

XCPC宇宙的的大学僧们在科研学习过程中发现不同类系的学习节点往往有不同的特性：

开发学习节点往往可以比较独立的进行，没有过多前置知识的依赖，但是它们往往比较值得被多次多次学习，因此对于某一个该类型学习节点最多可以学习 $amount_i$ 次
科研学习组中的一些子类型在学习之前是需要前置知识的，当你学完某一个子类型的所有前置子类型知识的所有学习次数之后或者某一个子类型没有前置子类型知识才可以学该子类型，而且一个科研学习组子类型总是只需要学习 $1$ 次。一共有 $m$ 条子类型之间的依赖关系：
- 每一组有关联的科研学习节点个数都不超过 $10$ 个
- 每一组有关联的科研学习节点中，每一个学习节点的依赖关系的入度和出度都小于 $\text 2$

对于第i个大学僧学习完成之后，总能力值为 $ability$

开发学习组 $group = 1$ : 每学习一次该group下的某个子类型一次，花费 $cost_i$ 个小时时间，使得 $ability += b* a_i$ ，可以学习任意次，但是最多 $amount_i$ 次

科研学习组 $group = 2$ : 每学习一次该group下的第i个子类型一次，花费 $cost_i$ 个小时时间，使得 $ability += c * a_i$ ，只能学习 $\text 1$ 次

每一个大学僧都单纯的努力提升自己，以尽可能提升自己的能力值为唯一目标，在提升过程中并不关注能力的类型。但是当他们在毕业面临选择的时候，每个大学僧又会回过头根据已经获得的能力值的组成部分，科研能力值 $ability_{科研能力}$ 以及开发能力值 $ability_{实现能力}$ 进行选择。选择规则如下：

当 $ability_{科研能力} > ability_{开发能力}$ ，该僧选择科研；
当 $ability_{科研能力} < ability_{开发能力}$ ，该僧选择开发。
当 $ability_{科研能力} = ability_{开发能力}$ ，若 $\mathit n$ 为奇数，该僧选择科研，反之选择开发。

第一行输入三个整数 $b,c,total_time(1≤b,c≤10^6,1≤totalTime≤10^5)$ --该大学僧的开发兴趣加成 , 科研兴趣加成 , 总学习时间

第二行输入两个整数 $n,m(1≤n≤10^3,1≤m≤10^4)$ --该大学僧的学习节点数量 , 该大学生科研学习节点依赖关系数

接下去 $\mathit n$ 行，第 $\mathit i$ 行先输入三个整数 $group_i,cost_i,a_i(1≤group_i≤2,1≤cost_i≤10^5,1≤a_i≤10^6)$ --该大学僧第 $i$ 个学习节点的组类别 , 单次学习花费时间 , 单次学习获得的改组能力值

- 当且仅当 $group_i=1$ 时，第 $i$ 行再输入一个整数 $amount_i(1≤amount_i≤10^3)$ --最多学习开发学习组该子类型的次数

接下去 $\mathit m$ 行，第 $\mathit i$ 行输入两个整数 $x_i,y_i(1≤x_i,y_i≤n,x_i ≠ y_i)$ --表示 $x_i$ 为 $y_i$ 的科研学习前置知识

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10,M = 1e5+10; ll b,c,tot; struct Node{ int g,num,cost,a; }; vector<Node> vec; int w[M],v[M],cnt[M]; ll dp1[M]; void solve1(){ int id = 0; for(auto & i : vec){ if(i.g==2) continue; int ww = i.cost, vv = i.a, num = i.num; int p = 1; while(num){ if(num-p>0){ w[++id] = ww*p, v[id] = vv*p, num-=p; p*=2; } else break; } if(num) w[++id] = ww*num, v[id] = vv*num; } for(int i=1;i<=id;i++){ for(int j = (int)tot;j>=w[i];j--){ dp1[j]=max(dp1[j],dp1[j-w[i]]+v[i]); } } } vector<int> g[N]; int in[N]; ll sumv[N][100],sumw[N][100]; ll dp2[M]; int dfs(int u,int x,int f){ for(int vv : g[u]){ sumv[f][x+1] = sumv[f][x]+ vec[vv].a; sumw[f][x+1] = sumw[f][x]+ vec[vv].cost; return dfs(vv,x+1,f); } return x; } void solve2(int n){ for(int i=1;i<=n;i++){ if(in[i]==0&&vec[i].g==2){ sumv[i][1] = vec[i].a; sumw[i][1] = vec[i].cost; cnt[i] = dfs(i,1,i); } else cnt[i]=0; } for(int i=1;i<=n;i++) for(int j=(int)tot;j>=0;j--) for(int k=0;k<=cnt[i];k++){ if(sumw[i][k]<=j) dp2[j] = max(dp2[j],dp2[j-sumw[i][k]]+sumv[i][k]); } } int main(){ int n,m; scanf("%lld%lld%lld",&b,&c,&tot); scanf("%d%d",&n,&m); vec.push_back({0,0,0,0}); for(int i=1;i<=n;i++){ int gou,num,cost,a; scanf("%d",&gou); scanf("%d%d",&cost,&a); if(gou==1) scanf("%d",&num); vec.push_back({gou,num,cost,a}); } for(int i=1,x,y;i<=m;i++){ scanf("%d%d",&x,&y); g[x].push_back(y); in[y]++; } solve1(); solve2(n); ll res=0,resid; //开发：1，科研：2 for(int i=0;i<=tot;i++){ if(b*dp1[i]+c*dp2[tot-i]>res){ res = b*dp1[i]+c*dp2[tot-i]; if(b*dp1[i]>c*dp2[tot-i]) resid = 1; else if(b*dp1[i]<c*dp2[tot-i]) resid = 2; else resid = (n&1)+1; } } printf("%s\n",(resid==1)?"Development":"Scientific Research"); }

详情