P10561 [ICPC 2024 Xi’an I] Smart Quality Inspector题目描述Ella 有一家工厂。一天她的工厂面临产品质量检查。 她的工厂有NNN条生产线。在这NNN条生产线中有N−KN-KN−K条是合格的另外KKK条是不合格的。第iii条1≤i≤K1\leq i\leq K1≤i≤K不合格生产线的罚款为iii元。 这里有MMM名质量检查员。对于第jjj名1≤j≤M1\leq j\leq M1≤j≤M质量检查员他将检查从第lil_ili​条到第rir_iri​条的生产线并在其中找到罚款最高的不合格生产线然后将此罚款施加给 Ella。 Ella 不想收到太多罚款所以她决定重新编号这NNN条生产线以使收到的罚款最少。请帮助她。 简单来说 你有一个长度为NNN的序列AAAA[1,2,3,...,K,0,0,0,...,0]A[1,2,3,...,K,0,0,0,...,0]A[1,2,3,...,K,0,0,0,...,0]。这里N,KN,KN,K已知。 有MMM对整数每对由两个数字li,ril_i,r_ili​,ri​组成。 你需要重新排列序列AAA以最小化以下值∑i1Mmax⁡jliri(Aj)\sum_{i1}^M \max_{jl_i}^{r_i} (A_{j})i1∑M​jli​maxri​​(Aj​)输入格式第一行包含三个整数N,K,M(1≤K≤N≤20,1≤M≤105)N,K,M(1\leq K\leq N\leq 20,1\leq M\leq 10^5)N,K,M(1≤K≤N≤20,1≤M≤105)如题所述。 接下来MMM行每行包含两个整数li,ri(1≤li≤ri≤N)l_i,r_i(1\leq l_i\leq r_i\leq N)li​,ri​(1≤li​≤ri​≤N)。输出格式一个整数表示答案。输入输出样例 #1输入 #14 4 3 1 2 3 4 1 4输出 #110说明/提示由 ChatGPT 4o 翻译C实现#includebits/stdc.husingnamespacestd;intn,k,m,l,r,ans1e9,pre[25][25],f[2000010],lst[25],nxt[25];intmain(){scanf(%d%d%d,n,k,m);for(inti1;im;i){scanf(%d%d,l,r);pre[l][r];}for(inti1;in;i){for(intj1;jn;j){pre[i][j]pre[i][j]pre[i][j-1]pre[i-1][j]-pre[i-1][j-1];}}for(intS1;S(1n);S){inttot0;for(inti0;in;i){if((Si)1)tot;}if(totk)continue;f[S]1e9,lst[0]0,nxt[n1]n1;for(inti0;in;i){if((Si)1)lst[i1]i1;elselst[i1]lst[i];}for(intin-1;i0;i--){if((Si)1)nxt[i1]i1;elsenxt[i1]nxt[i2];}for(inti0;in;i){if(!((Si)1))continue;intTS-(1i);intstlst[i],ednxt[i2]-2;intadpre[i1][ed1]-pre[st][ed1]-pre[i1][i]pre[st][i];f[S]min(f[S],f[T]ad*(k-tot1));}if(totk)ansmin(ans,f[S]);}printf(%d\n,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容