day1

因为noip寄了，所以非常伤心，准备从2023开始加油！刷题！
今天是洛谷P1267
首先，枚举根节点，下一次选的点的值在1~4nn中，每选一个点，在该子树中的选点范围就会缩小，此时我们考虑用搜索，但它应该过不了，再考虑dp，f[i][j][k]表示以i为子树的根节点，以[j,k]为子树的选数范围，但ijk=(4nn)^3，依然过不了，但是对于一个以i根节点的子树来说，它选数范围的左端点或右端点一定是i的父结点的值，且每一个结点的父节点的可能性只有三个，因此记搜加map可过。
代码：

#include<iostream>
#include<map>
#include<cmath>
#define int long long
using namespace std;
int n;
struct node{
	int to;
	int nxt;
}edge[10010];
int head[4010],tot;
void addedge(int u,int v){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
int dian[4010];
map<pair<int,pair<int,int> >,int> mp;
int f[5][4][20];
int dfs(int u,int l,int r){
	if(mp[make_pair(u,make_pair(l,r))]!=0)return mp[make_pair(u,make_pair(l,r))];
	int zuo=0;
	int you=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(dian[v]>=l&&dian[v]<dian[u]){
			zuo=max(zuo,dfs(v,l,dian[u]-1));
		}
		if(dian[v]>dian[u]&&dian[v]<=r){
			you=max(you,dfs(v,dian[u]+1,r));
		}
	}
	return mp[make_pair(u,make_pair(l,r))]=1+zuo+you;
}
signed main(){
	cin>>n;
	for(int i=1;i<=4;i++){
		for(int j=1;j<=n*n;j++){
			cin>>dian[(i-1)*n*n+j];
		}
		for(int j=1;j<=n*n;j++){
			if((int)(sqrt(j))*(int)(sqrt(j))!=j){
				addedge((i-1)*n*n+j,(i-1)*n*n+j+1);
			}
			if((int)(sqrt(j-1))*(int)(sqrt(j-1))!=j-1){
				addedge((i-1)*n*n+j,(i-1)*n*n+j-1);
			}
			int heng=sqrt(j-1)+1;
			if((heng+j)%2==0){
				if(heng<n){
					addedge((i-1)*n*n+j,(i-1)*n*n+j+2*heng);
				}
			}
			else{
				if(heng>1){
					addedge((i-1)*n*n+j,(i-1)*n*n+j-2*heng+2);
				}
			}
		}
		for(int j=0;j<=n;j++){
			f[i][2][j]=(i-1)*n*n+j*j;
		}
		for(int j=1;j<=n;j++){
			f[i][1][j]=f[i][2][j-1]+1;
		}
		for(int j=1,k=f[i][1][n];j<=n;j++,k+=2){
			f[i][3][j]=k;
		}
	}
	for(int i=1;i<=n;i++){
		addedge(f[1][2][i],f[2][1][i]);
		addedge(f[2][1][i],f[1][2][i]);
		addedge(f[1][1][i],f[3][2][i]);
		addedge(f[3][2][i],f[1][1][i]);
		addedge(f[3][1][i],f[2][2][i]);
		addedge(f[2][2][i],f[3][1][i]);
		addedge(f[2][3][i],f[4][2][i]);
		addedge(f[4][2][i],f[2][3][i]);
	}
	for(int i=1,j=n;i<=n;i++,j--){
		addedge(f[1][3][i],f[4][1][j]);
		addedge(f[4][1][j],f[1][3][i]);
		addedge(f[3][3][i],f[4][3][j]);
		addedge(f[4][3][j],f[3][3][i]);
	}
	int ans=0;
	for(int i=1;i<=4*n*n;i++){
		ans=max(ans,dfs(i,1,4*n*n));
	}
	cout<<ans;
	return 0;
}

我对搜索和dp有一些小小的想法，搜索复杂度爆炸是一个状态询问多次，dp复杂度爆炸是询问许多无用状态，个人认为记搜加map可以解决，当然，dp经过一定处理也可以完成。除此以外，dp的状态查询大部分都是有一定顺序的，若是排不出顺序的，可以用搜索解决。