本文共 1238 字，大约阅读时间需要 4 分钟。

题意

一道题有$k$个测试点,共提交了$n$次

每次提交是一个长为$k$的$01$串,表示是否能通过第$i$个测试点

现在要求你重新排序$k$个测试点,使得$\sum _{i=1}^{n}w[i]$最小

其中$w[i]$指的是第$i$个人第一次在第几个测试点$wronganswer$了

输出字典序最小的方案数

考虑定义$f[i]$表示当放置测试点状态为$i$时,能得到的最小代价

那么枚举本次放的是第$j$道题,放置之后由状态$v$转移到状态$u$

造成的代价是$num(u)$($u$的二进制位是$1$的个数,表示在这个测试点$wa$掉)

因为在之前的$num(u)-1$个测试点都没有$wa$掉,在第$num(u)$个测试点$wa$掉

我们需要求满足要求的提交个数也就是$u$的超集,再减去$v$的超集,那么计算出这次转移的代价$val$

$$f[u]=min(f[u],f[v]+val)$$

记录一个前驱就可以转移了

#include 
   
    using namespace std;const int maxn = 2e6+10;const int inf = 1e9;int t,n,T,num[maxn],pre[maxn],cnt[maxn],f[maxn],bit[maxn];string s[maxn];void sosdp(){
   	for(int i=1;i<=n;i++)	cnt[num[i]]++;	for(int i=0;i
    
     =0;i--)	{
   		for(int j=1;j<=t;j++)//枚举每一个测试点		{
   			if( i&(1<<(j-1)) )			{
   				int v = i ^ (1<<(j-1)), val = f[i] + ( cnt[v]-cnt[i] )*bit[i];				if( val
     
      >1] + (i&1);	cin >> T;	while( T-- )	{
   		cin >> t >> n;		for(int i=1;i<=n;i++)		{
   			cin >> s[i];			int x = 0;			for(int j=0;j
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116131881 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！