1 条题解
-
0
前言
一个感觉很假的做法,赛时写挂了,但是赛后改改改过了 System test。
没注意到 Luogu 爬了 CF。既然爬了,我就发一下吧。
思路
就,你考虑一个贪心:每个数组都和可能与它组合成答案的算一遍。
然后可能和它构成答案的数满足一个贪心的性质。
即:
- 差异为 的只用保留最小一个。
- 差异为 的只用保留最小两个。
- 以此类推。
然后这个阈值我不太会算,于是口胡了一个
Lim
数组:const uint Lim[]={0,1,5,15,40,100};
Code
放一下核心代码。
uint W[100005],A[100005][5],Ans[6][6]; std::vector<uint>QAQ; typedef std::pair<uint,uint>Pair; Pair P[6][6]; uint m; uint lcs(uint a,uint b) { for(uint i=0;i<m;i++)for(uint j=0;j<m;j++) if(A[a][i]==A[b][j])Ans[i+1][j+1]=Ans[i][j]+1,P[i+1][j+1]=Pair(i,j); else Ans[i+1][j+1]=std::max(Ans[i+1][j],Ans[i][j+1]), P[i+1][j+1]=Ans[i+1][j]>Ans[i][j+1]?Pair(i+1,j):Pair(i,j+1); QAQ.clear(); Pair now=Pair(m,m); while(now!=Pair()) { if(P[now.first][now.second].first<now.first &&P[now.first][now.second].second<now.second) QAQ.push_back(A[a][now.first]); now=P[now.first][now.second]; } return Ans[m][m]; } uint Id[100005],Now[100005],cnt=0; const uint Lim[]={0,1,5,15,40,100}; int main() { uint n;uint ans=-1; scanf("%u%u",&n,&m); for(uint i=0;i<n;i++) { for(uint j=0;j<m;j++)scanf("%u",A[i]+j); scanf("%u",W+i); std::sort(A[i],A[i]+m); Id[i]=i; } std::sort(Id,Id+n,[&](uint a,uint b){return W[a]<W[b];}); for(uint i=0;i<n;i++) { uint p=Id[i]; std::map<std::vector<uint>,uint>LCNT; for(uint j=0;j<cnt;j++) { uint c=lcs(p,Now[j]); LCNT[QAQ]++; if(!c)_min(ans,W[p]+W[Now[j]]); } bol b=true; for(auto p:LCNT) if(p.second>Lim[m-p.first.size()]){b=false;break;} if(b)Now[cnt++]=p; } printf("%d\n",(int)ans); return 0; }
- 1
信息
- ID
- 7694
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者