ARC207A Affinity for Artifacts 题解

设总成本为

w

，第

i

个灯是第

p_i

个被点亮的。考虑每个灯节约了多少成本，则显然有：

\left(\sum_{i=1}^n a_i\right)-w=\sum_{i=1}^n \min(a_i,p_i-1)

考虑把

a_i

看作

1

类数，

p_i-1

看作

2

类数，将所有

a_i

和所有

p_i-1

扔进一个长度为

2n

的数列

c

中并从大到小排序，每次选出一个

1

类数和

2

类数进行匹配，贡献为较小的数的值。

设

f_{i,j,k}

表示考虑到数列

c

的第

i

项，此时一共匹配了

j

对数，总贡献为

k

的方案数。转移时，首先根据

i,j

和前缀和数组，计算出未匹配的

1

类数数量

x

和未匹配的

2

类数数量

y

，再根据

c_{i+1}

的类型分别处理：

若 $c_{i+1}$ $c_{i + 1}$ 为 $1$ $1$ 类数：
- 若 $y>0$ ：对 $c_{i+1}$ 进行匹配， $f_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+y \times f_{i,j,k}$ ；
- 不对 $c_{i+1}$ 进行匹配， $f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}$ 。
若 $c_{i+1}$ $c_{i + 1}$ 为 $2$ $2$ 类数：
- 若 $x>0$ ：对 $c_{i+1}$ 进行匹配， $f_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+x \times f_{i,j,k}$ ；
- 不对 $c_{i+1}$ 进行匹配， $f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}$ 。

初始化

f_{0,0,0}=1

。设

v=\left(\sum\limits_{i=1}^n a_i\right)-x

，特判一下

v \lt 0

和

v \gt \frac {n(n-1)}2

的情况，答案即为

\sum\limits_{i=v}^{\frac{n(n-1)}{2}} f_{2n,n,i}

。

时间复杂度

\mathcal O(n^4)

。

const int N=105,mod=998244353;
int n,x,a[N],s[N<<1][3],f[N<<1][N][N*(N-1)/2];
ll sum,v;
pii p[N<<1];
int get(int i,int j){
	int a=s[i][1],b=s[i][2];
	return b-a+j;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	v=sum-x;
	if(v<0) v=0;
	if(v>n*(n-1)/2) v=n*(n-1)/2+1;
	for(int i=1;i<=n;i++) p[i]={a[i],1},p[n+i]={i-1,2};
	sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
	for(int i=1;i<=n+n;i++) for(int j=1;j<=2;j++) s[i][j]=s[i-1][j]+(p[i].se==j);
	f[0][0][0]=1;
	for(int i=0;i<n+n;i++){
		for(int j=0;j<=min(s[i][1],s[i][2]);j++){
			int x=s[i][1]-j,y=s[i][2]-j;
			for(int s=0;s<=n*(n-1)/2;s++){
				if(p[i+1].se==1){
					if(y!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*y%mod);
					add(f[i+1][j][s],f[i][j][s]);
				}
				else{
					if(x!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*x%mod);
					add(f[i+1][j][s],f[i][j][s]);
				}
			}
		}
	}
	int ans=0;
	for(int i=v;i<=n*(n-1)/2;i++) add(ans,f[n+n][n][i]);
	cout<<ans<<endl;
}

ARC207A Affinity for Artifacts 题解

文章操作

相关推荐

评论

ARC207A Affinity for Artifacts 题解