推荐好的设计网站盐城网站建设制作

推荐好的设计网站,盐城网站建设制作,免费好用的企业邮箱,wordpress添加自定义字段题目翻译与分析 游戏规则理解 《鹰巢》是一款非线性剧情的动作冒险游戏。玩家需要从简单任务开始#xff0c;通过完成越来越难的任务#xff0c;最终挑战最困难的任务。游戏的核心机制如下#xff1a; 任务难度与顺序 #xff1a;每个任务有一个难度值#xff0c;任务按输…题目翻译与分析游戏规则理解《鹰巢》是一款非线性剧情的动作冒险游戏。玩家需要从简单任务开始通过完成越来越难的任务最终挑战最困难的任务。游戏的核心机制如下任务难度与顺序每个任务有一个难度值任务按输入顺序给出这代表了它们在剧情中的顺序。任务选择限制在单次游戏流程中玩家只能选择难度严格大于所有已完成任务难度的任务。这意味着在单次流程中完成的任务难度必须是严格递增的。任务完成状态一个任务一旦在单次流程中完成在该次流程中就不能再次选择。首尾任务特殊性第一个任务最简单和最终任务最困难不计入任务总数并且总是可以被访问。它们相当于固定的起点和终点。游戏可重复性玩家可以多次从头开始游戏。每次游戏都从第一个任务开始到最终任务结束。目标设KKK为玩家第一次玩游戏时能够完成的最大任务数不包括首尾任务。玩家的目标是通过多次游戏在不重复完成任何任务的前提下最大化完成的任务总数。最终答案就是这个最大总数。问题转化与建模理解规则后我们可以将问题分解为两个关键步骤确定单次流程的最大任务数KKK在单次游戏中由于只能选择难度递增的任务且不能重复那么能完成的任务序列本质上就是原任务序列的一个严格递增子序列。而第一次玩游戏时能完成的最大任务数KKK就是整个任务序列的最长严格递增子序列 (LIS\texttt{LIS}LIS)的长度。注意这里我们只关心难度值任务名称仅用于输入输出不参与计算。确定最大可重复流程数知道了KKK我们需要找出最多能进行多少次“游戏流程”使得每次流程都完成恰好KKK个任务一条从难度最低层到最高层的路径并且所有流程中没有任务被重复使用。这可以建模为一个图论问题将每个任务看作一个节点。如果任务iii的难度小于任务jjj的难度并且任务jjj在以iii结尾的LIS\texttt{LIS}LIS中的层级正好比iii大111即d[j] d[i] 1那么我们就建立一条从iii到jjj的有向边。这样就形成了一个有向无环图 (DAG\texttt{DAG}DAG)。在这个DAG\texttt{DAG}DAG中我们需要找到尽可能多的从“层级为111的节点”对应LIS\texttt{LIS}LIS起点到“层级为KKK的节点”对应LIS\texttt{LIS}LIS终点的路径并且这些路径之间没有公共节点即任务不重复。这正是DAG\texttt{DAG}DAG上的最大不相交路径覆盖问题。对于节点不相交的路径覆盖可以通过拆点 最大流来解决将每个任务节点uuu拆成入点uinu_{in}uin​和出点uoutu_{out}uout​并在它们之间连一条容量为111的边这保证了每个任务最多被使用一次。对于原图中的有向边(u,v)(u, v)(u,v)在流网络中连接uout→vinu_{out} \to v_{in}uout​→vin​容量为111。建立超级源点SSS连接SSS到所有层级为 1 的任务的入点容量为111。建立超级汇点TTT连接所有层级为KKK的任务的出点到TTT容量为111。计算从SSS到TTT的最大流其值就等于最大不相交路径的数量记为flowflowflow。计算最终答案每次流程完成KKK个任务最多能进行flowflowflow次流程因此能完成的最大任务总数为K×flowK \times flowK×flow。样例详解为了更直观地理解题目我们详细分析题目给出的两个样例样例输入1113 Rob_The_Cop 6 A_Petty_Thief 5 Meet_The_Boss 3任务难度序列[6, 5, 3]分析计算KKK虽然输入顺序是6 → 5 → 3难度递减但玩家可以按照难度递增的顺序玩先玩难度333然后玩难度555535 353最后玩难度666656 565。所以最长严格递增子序列是[3, 5, 6]长度K3K 3K3。构建图所有任务都在同一条LIS\texttt{LIS}LIS路径上因此只能形成一条完整的路径难度333层级111→ 难度555层级222→ 难度666层级333。最大流由于只有一条路径最大不相交路径数flow1flow 1flow1。最终答案K×flow3×13K \times flow 3 \times 1 3K×flow3×13。样例输入2223 Meet_The_Boss 3 Rob_The_Cop 6 A_Petty_Thief 5任务难度序列[3, 6, 5]分析计算KKK可能的递增序列有[3, 6]或[3, 5]长度都是222。注意不能玩[3, 6, 5]因为玩完难度666后难度565 656违反了规则。所以K2K 2K2。构建图任务层级难度333层级111难度666层级222难度555层级 2可能的边难度333→ 难度666难度333→ 难度555有两条潜在路径3 → 6和3 → 5最大流由于任务333只能被使用一次拆点容量为111所以只能选择其中一条路径flow1flow 1flow1。最终答案K×flow2×12K \times flow 2 \times 1 2K×flow2×12。样例输出Case #1: 3 Case #2: 2关键启示样例111和样例222包含了相同的三个任务只是输入顺序不同导致答案不同。这凸显了任务难度值本身比输入顺序更重要的规则特性。玩家可以跳过中间的任务只要保证每次新玩的任务都比之前所有玩过的任务都难即可。算法流程总结输入任务提取难度值数组vvv。动态规划计算LIS\texttt{LIS}LIS长度KKK同时记录每个任务在LIS\texttt{LIS}LIS中的层级d[i]d[i]d[i]即以该任务结尾的LIS\texttt{LIS}LIS长度。根据层级关系构建DAG\texttt{DAG}DAG并使用拆点法建立流网络。使用最大流算法如Dinic\texttt{Dinic}Dinic、Edmonds-Karp\texttt{Edmonds-Karp}Edmonds-Karp计算最大流flowflowflow。输出答案K×flowK \times flowK×flow。代码实现// The Eagles Nest// UVa ID: 10546// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intcaseNumber1;// 测试用例编号intN;// 任务数量while(cinNN!0){// 读取任务名称和难度vectorpairstring,intmissions(N);for(inti0;iN;i)cinmissions[i].firstmissions[i].second;// 提取难度值vectorintv(N);for(inti0;iN;i)v[i]missions[i].second;// 第一步计算最长严格递增子序列(LIS)的长度K并记录每个任务的层级d[i]vectorintd(N,1);// d[i]表示以任务i结尾的LIS长度intmaxLen1;// 即K值for(inti0;iN;i){for(intj0;ji;j){if(v[j]v[i]d[j]1d[i]){d[i]d[j]1;}}maxLenmax(maxLen,d[i]);}// 第二步构建网络流图求解最大不相交路径数// 节点编号0-源点1~N为任务入点N1~2N为任务出点2N1为汇点intsource0,sink2*N1;vectorvectorintcap(2*N2,vectorint(2*N2,0));// 任务拆点每个任务入点到出点容量为1保证每个任务只被用一次for(inti0;iN;i){cap[i1][i1N]1;}// 源点连接所有第一层任务d[i]1for(inti0;iN;i){if(d[i]1){cap[source][i1]1;}}// 所有最后一层任务d[i]K连接汇点for(inti0;iN;i){if(d[i]maxLen){cap[i1N][sink]1;}}// 根据层级关系连接任务如果v[i] v[j] 且 d[j] d[i] 1则连边for(inti0;iN;i){for(intji1;jN;j){if(v[i]v[j]d[j]d[i]1){// 从i的出点连接到j的入点cap[i1N][j1]1;}}}// Dinic 最大流算法autobfs[](vectorintlevel)-bool{fill(level.begin(),level.end(),-1);queueintq;q.push(source);level[source]0;while(!q.empty()){intuq.front();q.pop();for(intv0;vsink;v){if(level[v]-1cap[u][v]0){level[v]level[u]1;q.push(v);}}}returnlevel[sink]!-1;};functionint(int,int,vectorint)dfs[](intu,intflow,vectorintlevel)-int{if(usink)returnflow;for(intv0;vsink;v){if(level[v]level[u]1cap[u][v]0){intpusheddfs(v,min(flow,cap[u][v]),level);if(pushed0){cap[u][v]-pushed;cap[v][u]pushed;returnpushed;}}}return0;};intmaxFlow0;vectorintlevel(sink1);while(bfs(level)){while(intpusheddfs(source,INT_MAX,level)){maxFlowpushed;}}// 第三步计算最终答案 K * 最大不相交路径数intresultmaxLen*maxFlow;coutCase #caseNumber: resultendl;}return0;}