P10412 「QFOI R2」钟声远带斜阳题目描述注意本题中的所有数列下标从000开始。小 R 是一个可爱的女孩子她喜欢研究无穷数列。她称一个无穷数列bbb是美妙的当且仅当存在自然数k0k_0k0​使得对于所有k≥k0k\ge k_0k≥k0​都满足bbb中下标在区间[k0,k][k_0,k][k0​,k]内的所有数的和非负即∑ik0kbi≥0\sum_{ik_0}^kb_i\ge 0∑ik0​k​bi​≥0。例如数列αii−5\alpha_ii-5αi​i−5是美妙的取k05k_05k0​5符合要求但βi−i\beta_i-iβi​−i不是美妙的。她目前只有一个长度为nnn的有穷数列aaa可以进行任意次以下三种操作花费ppp的代价选择一个整数iii0≤in0\le i n0≤in将aia_iai​增加一。花费qqq的代价选择一个整数iii0≤in0\le i n0≤in将aia_iai​删除同时更新nnn为新的数列长度。不能将数列删空。花费rrr的代价选择两个整数i,ji,ji,j0≤ijn0\le i j n0≤ijn交换aia_iai​与aja_jaj​。她希望在若干次操作后用无限个有穷数列aaa依次相接得到无穷数列bbb即biai mod nb_ia_{i\bmod n}bi​aimodn​使得bbb是美妙的。请你求出最小的代价。输入格式第一行四个整数n,p,q,rn,p,q,rn,p,q,r。第二行nnn个整数表示数列aaa。输出格式一行一个整数表示最小代价。输入输出样例 #1输入 #15 1 2 5 2 -2 3 -3 -1输出 #11输入输出样例 #2输入 #25 2 1 5 2 -2 3 -3 -1输出 #21输入输出样例 #3输入 #35 1 1 1 0 1 2 3 4输出 #30说明/提示样例111解释花费p1p1p1的代价将a3a_3a3​增加一得到数列b[2,−2,3,−2,−1,2,−2,3,−2,−1,⋯ ]b[2,-2,3,-2,-1,2,-2,3,-2,-1,\cdots]b[2,−2,3,−2,−1,2,−2,3,−2,−1,⋯]是美妙的取k02k_02k0​2符合要求。可以证明不存在代价更小的方案。样例222解释花费q1q1q1的代价将a1a_1a1​删除得到数列b[2,3,−3,−1,2,3,−3,−1,⋯ ]b[2,3,-3,-1,2,3,-3,-1,\cdots]b[2,3,−3,−1,2,3,−3,−1,⋯]是美妙的取k00k_00k0​0符合要求。可以证明不存在代价更小的方案。数据范围本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务才能获得相应的分数。对于全部数据1≤n≤1051\le n\le 10^51≤n≤1051≤p,q,r≤1091\le p,q,r\le 10^91≤p,q,r≤109∣ai∣≤109|a_i|\le 10^9∣ai​∣≤109。子任务一101010分n1n1n1。子任务二101010分n≤10n\le 10n≤10。依赖子任务一。子任务三202020分∣ai∣≤1|a_i|\le 1∣ai​∣≤1。子任务四202020分∑∣ai∣≤105\sum|a_i|\le 10^5∑∣ai​∣≤105。依赖子任务三。子任务五404040分无特殊限制。依赖子任务一、二、三、四。C实现#includebits/stdc.husingnamespacestd;constintN100010;longlongn,p,q,r,sum,ans,a[N];//要开 long longboolftrue;//判断之前有没有用过修改操作intmain(){cinnpqr;for(inti1;in;i){cina[i];suma[i];}if(sum0){cout0endl;return0;}sort(a1,an1);for(inti1;in;i){longlongtmin(-sum,-a[i]);if(qt*p)//如果删除操作更优{ansq;sumt;}else//如果修改操作更优{anst*p;sumt;ffalse;}if(sum0)break;}if(a[n]0)//不能删空{if(f)//如果之前都是删除操作说明 a数组中只有啊 a[n]这一个数ans(-a[n])*p;elseansmin(q,(-a[n]*p));}coutansendl;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容