45 分做法

直接输出不用魔法点的答案，第一问是 $2\times n\times w_1$，第二问是 $\dbinom{2n}{n}$。

25 分做法

如果使用魔法点更优，则用的越多越好。然后就转化成了二维的最长上升子序列问题。这里的“上升”指 $\forall i<j, x_i<x_j ~and~y_i<y_j$ 。

当 $k$ 比较小的时候，设计 $f_i$ 表示以 $i$ 结尾的最长上升子序列长度，$g_i$ 表示以 $i$ 为结尾的方案数。先按照 $x$ 在按照 $y$ 排序，转移条件是 $x_i \ne x_j ~and~ y_i>y_j$。

然后这个时候如果把第一种情况写错了，你就会 25 分做法了。

具体代码可以参考我赛时代码。

70 分做法

把前两个合起来，注意第一种情况别写错了。

如果 $k$ 过大直接输出第一种情况的答案。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
const int N=500005,mod=1000000007;
int n,w1,w2,k;
struct node {
	int x,y;
} a[N];
bool cmp(node A,node B) {
	if(A.x==B.x)return A.y<B.y;
	return A.x<B.x;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}return res;
}
int f[N],g[N];
signed main() {
//	freopen("grid.in","r",stdin);
	R(n),R(k),R(w1),R(w2);
	for(int i=1; i<=k; ++i) R(a[i].x)+1,R(a[i].y)+1;
	sort(a+1,a+1+k,cmp);
	g[0]=1;
  if(k<=5000)
	for(int i=1; i<=k; ++i) {
		for(int j=0; j<k; ++j) {
			if(a[i].y>a[j].y&&a[i].x!=a[j].x) {
				if(f[i]<f[j]+1) {
					f[i]=f[j]+1;
					g[i]=g[j];
				} else if(f[i]==f[j]+1) {
					g[i]=(g[i]+g[j])%mod;
				}
			}
		}
	}
	int len=0;
	for(int i=1; i<=k; ++i) {
		len=max(len,f[i]);
	}
	int cost1=2*n*w1,cost2=cost1+len*(w2-2*w1);
	if(cost1<cost2||k>5000){
		int fac1=1,fac2=1;
		for(int i=1;i<=2*n;++i){
			fac2=fac2*i%mod;
			if(i<=n) fac1=fac1*i%mod;
		}
		int inv1=ksm(fac1,mod-2);
		cout<<cost1<<"\n"<<fac2*inv1%mod*inv1%mod;
		return 0;
	}
	int ans=0;
	for(int i=1;i<=k;++i){
		if(len==f[i]) ans=(ans+g[i])%mod;
	}
	cout<<cost2<<"\n"<<ans;
	return 0;
}

满分做法

复杂度瓶颈在于 $\mathcal O(k^2)$ 的状态转移。这个看着挺像二维数点。首先，如果 $x$ 一样，$y$ 降序排，这样就不用判 $x_i\ne x_j$ 了。

然后现在只有 $y$ 这一个偏序关系要处理。我们使用树状数组优化 DP。

树状数组需要维护长度和方案，要支持以下两个操作：

• add(x,f,g)，把 $(x,f_x,g_x)$ 加入树状数组。

• ask(x)，找出下标 $\le x$ 的最大长度和方案。

然后把 DP 部分改一下就行了。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
const int N=500005,mod=1000000007;
int n,w1,w2,k;
struct node {
	int x,y;
} a[N];
bool cmp(node A,node B) {
	if(A.x==B.x)return A.y>B.y;
	return A.x<B.x;
}
int ksm(int a,int b) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int f[N],g[N];
int tf[N],tg[N];
#define lb(x) (x&(-x))
void add(int x,int f,int g){
	while(x<=n){
		if(f>tf[x]) tf[x]=f,tg[x]=g;
		else if(f==tf[x]) tg[x]=(tg[x]+g)%mod;
		x+=lb(x);
	}
}
pair<int,int>ask(int x){
	int f=0,g=0;
	while(x){
		if(tf[x]>f) f=tf[x],g=tg[x];
		else if(tf[x]==f) g=(g+tg[x])%mod;
		x-=lb(x);
	}
	return {f,g};
}
signed main() {
//	freopen("grid.in","r",stdin);
	R(n),R(k),R(w1),R(w2);
	for(int i=1; i<=k; ++i) R(a[i].x)+2,R(a[i].y)+2;
	sort(a+1,a+1+k,cmp);
	add(1,0,1);
	for(int i=1; i<=k; ++i) {
		pair<int,int>pii=ask(a[i].y-1);
		f[i]=pii.first+1,g[i]=pii.second;
		add(a[i].y,f[i],g[i]);
	}
	int len=0;
	for(int i=1; i<=k; ++i) {
		len=max(len,f[i]);
	}
	int cost1=2*n*w1,cost2=cost1+len*(w2-2*w1);
	if(cost1<cost2) {
		int fac1=1,fac2=1;
		for(int i=1; i<=2*n; ++i) {
			fac2=fac2*i%mod;
			if(i<=n) fac1=fac1*i%mod;
		}
		int inv1=ksm(fac1,mod-2);
		cout<<cost1<<"\n"<<fac2*inv1%mod*inv1%mod;
	} else {
		int ans=0;
		for(int i=1; i<=k; ++i) {
			if(len==f[i]) ans=(ans+g[i])%mod;
		}
		cout<<cost2<<"\n"<<ans;
	}
	return 0;
}

关于二维数点这里推荐几道题P10589，P10814,P3755

P3755加强一下就是P4390（多考虑时间作为第三维，不过就是用cdq了）

0分做法

这是0分做法

10分做法

暴力dfs

void dfs(int idx,int idy,bool flg,int cnt){
	if(idx==n&&idy==n){
		if(flg){
			if(ans>cnt){
				ans=cnt,dns=cns=1;
				mp.clear(),mp[pth[idx][idy]]=1;
			}
			else if(ans==cnt){
				if(!mp[pth[idx][idy]]) mp[pth[idx][idy]]=1,cns++;
			}
		}else{
			if(ans>cnt) ans=cnt,dns=0,bns=1;
			else if(ans==cnt) bns++;
		}
	}
	for(int i=0;i<2;i++){
		int x=idx+dx[i],y=idy+dy[i];
		if(x>n||y>n||x<0||y<0) continue;
		pth[x][y]=pth[idx][idy];
		dfs(x,y,flg,cnt+w1);
	}if(vis[idx][idy]){
		int x=idx+1,y=idy+1;
		if(x>=0&&x<=n&&y>=0&&y<=n){
			char px=x+'0',py=y+'0';
			pth[x][y]=pth[idx][idy]+"(";
			pth[x][y]+=px;pth[x][y]+=",";
			pth[x][y]+=py;pth[x][y]+=")";
			dfs(x,y,1,cnt+w2);
		}
	}
}

时间复杂度 $O(不能过)$

20分做法

发现我们会使用 $w2$ 当且仅当 $w2=2\times w1$ 时我们才会使用，所以当 $w1=w2$ 的时候直接输出 $n\times w2$ 和 $1$

printf("%d\n1\n",n*w2);

45分做法

第三档是何意味？

计算不需要魔法点的答案，第一问显然是 $2\times n\times w1$ ，第二问我们可以考虑使用dp算出，我们发现这个dp数组实际上就是杨辉三角，观察一下发现答案是 $C_{2\times n}^{n}$

70分做法

我们考虑这样一个贪心，如果我们当前选魔法点更优的话那我们一定要多选魔法点

首先我们先分别按照x和y升序排序

可以使用dp来完成，设 $dp_i$ 表示以 $i$ 为结尾的可以选的最多的魔法点

时间复杂度 $O(n^2)$

则有：

85分做法

何意味？

将树状数组的MAX函数写错即可

100分做法

我们发现70分做法瓶颈在于转移，转移条件是 $x_j<x_i$ 且 $y_j<y_i$

这就是一个二维偏序问题，我们考虑在 $x$ 相同时将 $y$ 倒序排序，使用树状数组维护

时间复杂度 $O(n\log n)$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=500005,mod=1e9+7;
int _=1,n,k,w1,w2,fac[N],inv[N],dp[N],g[N];
struct node{int x,y;}a[N];
struct AIbaobao{int f,g;}c[N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}
bool cmp(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;}
int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int lowbit(int x){return x&(-x);}
AIbaobao MAX(AIbaobao A,AIbaobao B){
	AIbaobao res=A;if(A.f<B.f) res=B;
	else if(A.f==B.f) res.g=(A.g+B.g)%mod;
	return res;
}
void add(int x,AIbaobao d){for(int i=x;i<=n;i+=lowbit(i)) c[i]=MAX(c[i],d);}
AIbaobao asks(int x){
	AIbaobao res={0,0};
	for(int i=x;i>0;i-=lowbit(i)) res=MAX(res,c[i]);
	return res;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),k=reads(),w1=reads(),w2=reads();
		for(int i=1;i<=k;i++) a[i].x=reads()+2,a[i].y=reads()+2;
		sort(a+1,a+k+1,cmp);
		if(w1+w1<w2){
			int ans=2*w1*n,bns;
			fac[0]=inv[0]=fac[1]=inv[1]=1;
			for(int i=2;i<N;i++) fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
			for(int i=1;i<N;i++) inv[i]=inv[i]*inv[i-1]%mod;
			bns=C(n+n,n);printf("%lld\n%lld\n",ans,bns);
		}else{
			int ans=0,bns=0,cnt=0;
			a[0].x=a[0].y=1;g[0]=1;
			add(1,AIbaobao{0,1});
			for(int i=1;i<=k;i++){
				AIbaobao now=asks(a[i].y-1);
				dp[i]=now.f+1,g[i]=now.g;
				add(a[i].y,AIbaobao{dp[i],g[i]});
			}for(int i=1;i<=k;i++) cnt=max(cnt,dp[i]);
			ans=2*w1*n-cnt*(w1+w1-w2);
			for(int i=1;i<=k;i++) bns=(bns+(dp[i]==cnt)*g[i])%mod;
			printf("%lld\n%lld\n",ans,bns);
		}
	}return 0;
}
/*
3 8 1 100
0 0
0 1
1 0
1 1
2 0
0 2
2 1
1 2

*/