当前位置：首页 > news >正文

打卡信奥刷题（3470）用C++实现信奥题 P10561 [ICPC 2024 Xi‘an I] Smart Quality Inspector

news 2026/7/26 12:34:25

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的序列AAA，A=[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以最小化以下值：∑i=1Mmax⁡j=liri(Aj)\sum_{i=1}^M \max_{j=l_i}^{r_i} (A_{j})i=1∑Mj=limaxri(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

输入 #1

4 4 3 1 2 3 4 1 4

输出 #1

说明/提示

（由 ChatGPT 4o 翻译）

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,k,m,l,r,ans=1e9,pre[25][25],f[2000010],lst[25],nxt[25];intmain(){scanf("%d%d%d",&n,&k,&m);for(inti=1;i<=m;i++){scanf("%d%d",&l,&r);pre[l][r]++;}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){pre[i][j]=pre[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];}}for(intS=1;S<(1<<n);S++){inttot=0;for(inti=0;i<n;i++){if((S>>i)&1)tot++;}if(tot>k)continue;f[S]=1e9,lst[0]=0,nxt[n+1]=n+1;for(inti=0;i<n;i++){if((S>>i)&1)lst[i+1]=i+1;elselst[i+1]=lst[i];}for(inti=n-1;i>=0;i--){if((S>>i)&1)nxt[i+1]=i+1;elsenxt[i+1]=nxt[i+2];}for(inti=0;i<n;i++){if(!((S>>i)&1))continue;intT=S-(1<<i);intst=lst[i],ed=nxt[i+2]-2;intad=pre[i+1][ed+1]-pre[st][ed+1]-pre[i+1][i]+pre[st][i];f[S]=min(f[S],f[T]+ad*(k-tot+1));}if(tot==k)ans=min(ans,f[S]);}printf("%d\n",ans);return0;}