O_O怎么是构造题

原题：LOJ6502

首先我们容易考虑$dp$，设$dp_{i,j}$表示前$i$个里面分$j$个到$A$队的方案数，然后直接转移。

但是我们无法计算新增加一头牛会增加多少答案，因为我们并不知道前$i-1$头牛中有多少是$>m-a_i$的。

所以考虑构造一个$a$的排列使得这个容易计算。

其实我觉得这里想到构造挺没道理的..

对于一段已排序的牛$a_{l...r}$，若$a_r+a_l \geq m$，则$a_r+a_{l+1...r-1} \geq m$，这是一个良好的性质。我们可以让$a_r$在$a_{l...r-1}$的后面。

而若$a_l+a_r<m$，则$a_l+a_{l+1...r-1}<m$，我们也可以让$a_l$在$a_{l+1...r}$的后面，这样$a_l$在计算时直接不造成贡献，也是良好的性质。

具体地，我们从$l=1,r=n$开始考虑，若$a_l+a_r \geq m$，则将$a_r$放在栈顶，否则将$a_l$放在栈顶，最后出栈就是一个具有良好性质的$a$的排列。

在$dp$时，分类讨论$a_i$时哪一种牛即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m,a[101000];
int b[101000],btt;
int f[2020][2020],g[2020][2020];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int l=1,r=n;
	for(int i=1;i<=n;i++){
		if(a[r]+a[l]>=m) b[++btt]=a[r--];
		else b[++btt]=a[l++];
	}
	for(int i=1;i<=n/2;i++){
		swap(b[i],b[n-i+1]);
	}
	f[0][0]=0;
	g[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(b[i]+b[i-1]>=m){
				if(j<=i-1) f[i][j]=f[i-1][j]+j;
				if(j) f[i][j]=max(f[i][j],f[i-1][j-1]+i-j);
				if(j<=i-1) if(f[i-1][j]+j==f[i][j]) g[i][j]+=g[i-1][j];
				if(j) if(f[i-1][j-1]+i-j==f[i][j]) g[i][j]+=g[i-1][j-1];
			}else{
				if(j<=i-1)f[i][j]=f[i-1][j];
				if(j) f[i][j]=max(f[i][j],f[i-1][j-1]);
				if(j<=i-1) if(f[i-1][j]==f[i][j]) g[i][j]+=g[i-1][j];
				if(j) if(f[i-1][j-1]==f[i][j]) g[i][j]+=g[i-1][j-1]; 
			}
			g[i][j]%=mod;
		}
	}
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++){
		if(f[n][i]>ans1) ans1=f[n][i],ans2=0;
		if(f[n][i]==ans1) ans2+=g[n][i];
		ans2%=mod;
	}cout<<ans1<<" "<<ans2;
	return 0;
}

转载

考虑没有办法直接 dp 的原因是每次决策把某个点放入 A 或者 B 中不能确定产生了多少贡献。

因此考虑若能将 a_i 适当排列，使得：

$∀i∈[1,n]$ 对于 $∀j∈[1,i)$

要么：$a_j + a_i ≥ m$

要么：$a_j + a_i < m$

那么每次某个点 x 加入 A 或者 B，根据 a_1+a_x 和 m 的大小关系，可知产生的贡献为 0 或者另一部分点集的大小。

那么考虑构造这个排列。

转载

中间一档部分分提示我们将所有的 a_i 排序。

考虑如果我们能构造出这样一个 a_i 的序列，使得该序列满足：对于任意的 i(1≤i≤n)，所有的j(1≤ j<i) 都满足a_i+a_j≥m 或者所有的j(1≤j<i) 都满足 a_i+a_j<m，那么我们就可以使用动态规划求解。

具体地，设fi,j 表示处理到了 a_i，且A 队中已有j 个元素能得到的最大贡献值。若 a_i 满足对于任意 j(1≤j<i) 有a_i+a_j≥m，那么考虑将a_i 放入A 队，则a_i 与前面所有放入 B 队的i−j 个元素都能配合默契，因此有 fi,j=fi−1,j−1+i−j；考虑放入 B 队，则a_i 与前面所有放入 A 队中的j 个元素都能配合默契，因此有 fi,j=fi−1,j+j，最终答案在两者间取 max。若a_i 满足对于任意j(1≤j<i) 有a_i+a_j<m，由于无论放入A 队还是B 队都不能造成贡献，因此转移为 fi,j=max{fi−1,j−1,fi−1,j}。

求方案数在转移 f 时一起统计即可。

现在的问题是如何构造这个序列。

我们先将 a 从小到大排序，发现若 a1+a_n≥m，那么对于任意的 j(1≤j<n) 均满足a_j+a_n≥m；若a1+a_n<m ，那么对于任意的j(1<j≤n) 均满足a1+a_j<m，但依然有可能存在 j(1≤j<n) 满足 a_j+a_n≥m。

因此，我们可以思考如下算法：

对于按从小到大排序后得到的区间 [l,r]（初始 l=1, r=n），若满足 a_l+a_r≥m，那么弹出 a_r，递归处理区间[l,r−1]；否则弹出 a_l，递归处理区间[l+1,r]。每次我们将弹出的数放到一个新的数组 p 的最左端，那么可以证明，得到的 p 数组就能够满足我们所需要的性质。

我们求出数组 p 后，就能够通过 dp 在 O(n2) 的时间内解决此题了。

转载

首先将 a[i] 排序

设 f[i][j] 表示前 i 头牛，其中有 j 头牛分在 A 队的最多 PK 对数。

则 a_ns1=max(f[n][j], j=0……n)

对于第 i 头牛，若分在 A 队：

f[i][j] <--- f[i-1][j-1]+chk[i]?i-j:0

若分在 B 队：

f[i][j] <--- f[i-1][j]+chk[i]?j:0

#include<cstdio>
#include<cstring>
#include<a_lgorithm>
using namespace std;

inline int read()
{
	int x=0;cha_r ch=getcha_r();
	ahile(ch<'0' || '9'<ch)ch=getcha_r();
	ahile('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getcha_r();
	return x;
}

typedef long long ll;
const int N=2009;
const int md=1e9+7;

int n,m,a_ns;
int a[N],c[N];
ll f[N][N],g[N][N];

inline bool chkmin(ll &a,ll b){if(a>b)return a=b,1;return 0;}
inline bool chkmax(ll &a,ll b){if(a<b)return a=b,1;return 0;}


inline ll qpoa(ll a,ll b)
{
	ll ret=1;
	ahile(b)
	{
		if(b&1)ret=ret*a%md;
		a=a*a%md;b>>=1;
	}
	return ret;
}

inline void update(ll &a,ll &b,ll c,ll d)
{
	if(chkmax(a,c))b=d;
	else if(a==c)(b+=d)%=md;
}

int ma_in()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	sort(a+1,a+n+1);

	int l=1,r=n;
	for(int i=n;i>=1;i--)
	{
		if(a[l]+a[r]<m)
			c[i]=0,l++;
		else
			c[i]=1,r--;
	}

	memset(f,128,sizeof(f));
	f[0][0]=0;g[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
		{
			f[i][j]=f[i-1][j]+c[i]*j;g[i][j]=g[i-1][j];
			if(j)
				update(f[i][j],g[i][j],f[i-1][j-1]+c[i]*(i-j),g[i-1][j-1]);
		}

	ll a_ns=-1e18,cnt=0;
	for(int i=0;i<=n;i++)
		update(a_ns,cnt,f[n][i],g[n][i]);
	printf("%lld %lld\n",a_ns,cnt);
	return 0;
}