社区讨论

并查集???

P1233木棍加工参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjrxlxp
此快照首次捕获于
2025/11/04 07:31
4 个月前
此快照最后确认于
2025/11/04 07:31
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
unsigned* dp;
bool* flag;
struct bar{
	unsigned short l,w,e;
	bar* fa;
	friend istream& operator >>(istream& in,bar& b)
	{
		in>>b.l>>b.w;
		return in;
	}
	bool judge(bar& c)
	{
		if(c.l>=l&&c.w>=w)
		{
			fa=&c;
			return true;
		}
		return false;
	}
	friend bool operator !=(bar k,bar s)
	{
		if(k.l!=s.l||k.w!=s.w) return true;
		return false;
	}
};
bar* find_root(bar k)
{
	if(*k.fa!=k) k.fa=find_root(*k.fa);
	return k.fa;
}
bar* b;
unsigned short cnt=1;
int main()
{
	ios::sync_with_stdio(false);
	unsigned short n;
	cin>>n;
	b=new bar[n+1];
	dp=new unsigned[n+2];
	flag=new bool[n+2];
	memset(dp,0,sizeof(unsigned)*(n+2));
	for(unsigned short i=1;i<=n;i++) cin>>b[i],b[i].fa=&b[i],b[i].e=i;
	for(unsigned short i=1;i<=n;i++)
	{
		for(unsigned short j=1;j<i;j++)
		{
			if(b[j].judge(b[i])) dp[j]=max(dp[i]+1,dp[j]);
		}
	}
	for(unsigned short i=1;i<=n;i++)
	{
		bar* f=find_root(b[i]);
		if(!flag[f->e]) flag[f->e]=true,cnt++;
	}
	cout<<cnt<<endl;
	delete[](b);
	delete[] dp;
	delete[] flag;
	return 0;
}
所以...... what happened?

回复

0 条回复,欢迎继续交流。

正在加载回复...