社区讨论
并查集???
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 条回复,欢迎继续交流。
正在加载回复...