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;
}