「雅礼集训 2018 Day4」Divide 题解

很nb的构造

思路

考虑dp，设 $f_{i,j}$ 表示前 $i$ 艘飞船有 $j$ 艘A队的飞船，但是如果直接转移发现我们记录的信息不够，难以转移。

那么此时假如记录更多信息，显然时间会超，所以我们考虑另一种方法——构造，构造出原 $w_i$ 的一个合法排列，使得dp状态可以转移。

那么什么情况下可以转移？如果我们只记录 $i,j$，那么当前这艘飞船要么可以和全部的前 $i-1$ 艘飞船匹配，即 $\forall j \in [1, i), w_i + w_j \ge m$，要么不能和前 $i-1$ 艘飞船匹配，即 $\forall j \in [1, i), w_i + w_j < m$。

考虑如下构造：

设构造后的数组为 $p_i$，先将 $w_i$ 升序排序，初始设 $l=1,r=n$，然后进行 $n$ 次比较：第 $i$ 次比较，如果 $w_l+w_r\ge m$，则将 1 放到当前 $p_i$ 的开头，即 $p_{n-i+1}$，否则 $w_l+w_r\ge m$ 则将 0 放到 $p_{n-i+1}$。

此时，对于一个 $p_i$，当 $p_i=0$ 时表示它与前 $i-1$ 个数无法匹配，当 $p_i=1$ 时表示它可以与前 $i-1$ 个数匹配。

证明：

假如当前 $w_l+w_r\ge m$，则新加的 $p_i=1$，由于 $w_r$ 已经可以和 $w_l$ 匹配，并且 $w_i$ 是升序的，所以 $w_i(l \le i < r)$ 都可以和 $w_r$ 匹配，满足 $p_i=1$ 的条件（前 $i-1$ 个数就是 $w_i(l \le i < r)$）。

假如当前 $w_l+w_r< m$，则新加的 $p_i=0$，由于 $w_l$ 不能和 $w_r$ 匹配，并且 $w_i$ 是升序的，所以 $w_i(l < i \le r)$ 都不可以和 $w_l$ 匹配，满足 $p_i=0$ 的条件（前 $i-1$ 个数就是 $w_i(l < i \le r)$）。

证毕。

那么此时按新排列的 $p_i$ 进行转移就是容易的。

当第 $i$ 艘飞船加入A队时，$f_{i,j}=f_{i-1,j-1}+[p_i=1]\cdot(i-j)$。

当第 $i$ 艘飞船加入B队时，$f_{i,j}=f_{i-1,j}+[p_i=1]\cdot j$。

最后统计方案数 $g_{i.j}$ 就是取两者中较大的，如果相同就都加起来。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m,a[2010],p[2010];
ll f[2010][2010],g[2010][2010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];//就是w_i 
	sort(a+1,a+1+n);
	int l=1,r=n;
	for(int i=n;i;i--){//构造p_i 
		if(a[l]+a[r]>=m){
			r--;p[i]=1;
		}
		else{
			l++;p[i]=0;
		}
	}
	g[0][0]=1;
	for(int i=1;i<=n;i++){//简单的dp 
		for(int j=0;j<=i;j++){
			if(j){
				ll v=f[i-1][j-1]+p[i]*(i-j);
				if(v>f[i][j]){
					f[i][j]=v;
					g[i][j]=g[i-1][j-1];
				}
				else if(v==f[i][j])g[i][j]=(g[i][j]+g[i-1][j-1])%mod;
			}
			if(j<i){
				ll v=f[i-1][j]+p[i]*j;
				if(v>f[i][j]){
					f[i][j]=v;
					g[i][j]=g[i-1][j];
				}
				else if(v==f[i][j])g[i][j]=(g[i][j]+g[i-1][j])%mod;
				
			}
		}
	}
	ll ans=0,cnt=0;
	for(int i=0;i<=n;i++){
		if(f[n][i]>ans){
			ans=f[n][i];cnt=g[n][i];
		}
		else if(f[n][i]==ans)cnt=(cnt+g[n][i])%mod;
	}
	cout<<ans<<" "<<cnt;
	return 0;
}