上升点列()

题目来源

CSP2022-J-T4

题解1，预计得分10分

数据分析，测试点1-2的n≤10,k=0。可采用傻傻的暴力得分
先取点后排序再判断是否符合题意
取点方法有两种：dfs和二进制，见链接
时间复杂度为指数级

数据分析，测试点1-2的n≤10,k=0。可采用傻傻的暴力得分
先取点后排序再判断是否符合题意
取点方法有两种：dfs和二进制，见链接
时间复杂度为指数级

#include<bits/stdc++.h>
using namespace std;
int n, k, ans=1;
struct node{
	int x, y;
}; 
node p[510], t[510];//p用于输入，t用于存放取出的点 
bool cmp(node a, node b){
	return a.x+a.y < b.x+b.y;
}
bool pd(int len){
	bool f=true;
	for(int i=1; i<len; i++)
		if(t[i].x+t[i].y-t[i-1].x-t[i-1].y != 1){
			f=false;break;
		}
	return f;
}
bool cni(int x, int y){//x个数取y个数，此处也可用dfs暴力选取
	bool f=false;
	for(int i=(1<<y)-1; i<(1<<x); i++){
		int num=0; int k=i;//num用于计数k的二进制位1的个数
		while(k){
			k=k&(k-1);
			num++;
		} 
		if(num==y){
			int cnt=0;
			memset(t, 0, sizeof(t));
			for(int j=0; j<x; j++)
				if(i&(1<<j))
					t[cnt++]=p[j];
			sort(t, t+cnt, cmp);
//			for(int w=0; w<cnt; w++)
//				cout<<t[w].x<<","<<t[w].y<<" ";
//			cout<<endl;
			if(pd(cnt))
				return true;
		} 
	}
	return f;
}
int main()
{
	cin>>n>>k;
	for(int i=0; i<n; i++)cin>>p[i].x>>p[i].y;
	for(int i=n; i>1; i--)
		if(cni(n, i))//从n个数中取出i个点 
		{
			ans=i;
			break;
		}
	cout<<ans;
	return 0;
}
/*
5 4
5 4
1 2
3 3
1 3
2 3
*/
————————

题目来源

CSP2022-J-T4

题解1，预计得分10分

数据分析，测试点1-2的n≤10,k=0。可采用傻傻的暴力得分
先取点后排序再判断是否符合题意
取点方法有两种：dfs和二进制，见链接
时间复杂度为指数级

数据分析，测试点1-2的n≤10,k=0。可采用傻傻的暴力得分
先取点后排序再判断是否符合题意
取点方法有两种：dfs和二进制，见链接
时间复杂度为指数级

#include<bits/stdc++.h>
using namespace std;
int n, k, ans=1;
struct node{
	int x, y;
}; 
node p[510], t[510];//p用于输入，t用于存放取出的点 
bool cmp(node a, node b){
	return a.x+a.y < b.x+b.y;
}
bool pd(int len){
	bool f=true;
	for(int i=1; i<len; i++)
		if(t[i].x+t[i].y-t[i-1].x-t[i-1].y != 1){
			f=false;break;
		}
	return f;
}
bool cni(int x, int y){//x个数取y个数，此处也可用dfs暴力选取
	bool f=false;
	for(int i=(1<<y)-1; i<(1<<x); i++){
		int num=0; int k=i;//num用于计数k的二进制位1的个数
		while(k){
			k=k&(k-1);
			num++;
		} 
		if(num==y){
			int cnt=0;
			memset(t, 0, sizeof(t));
			for(int j=0; j<x; j++)
				if(i&(1<<j))
					t[cnt++]=p[j];
			sort(t, t+cnt, cmp);
//			for(int w=0; w<cnt; w++)
//				cout<<t[w].x<<","<<t[w].y<<" ";
//			cout<<endl;
			if(pd(cnt))
				return true;
		} 
	}
	return f;
}
int main()
{
	cin>>n>>k;
	for(int i=0; i<n; i++)cin>>p[i].x>>p[i].y;
	for(int i=n; i>1; i--)
		if(cni(n, i))//从n个数中取出i个点 
		{
			ans=i;
			break;
		}
	cout<<ans;
	return 0;
}
/*
5 4
5 4
1 2
3 3
1 3
2 3
*/