社区讨论

奇怪的ac代码

P11233[CSP-S 2024] 染色参与者 3已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@m32z3f7k
此快照首次捕获于
2024/11/04 20:03
去年
此快照最后确认于
2025/11/04 15:21
4 个月前
查看原帖
我的考场代码大致如下所示:
问题1:我用的是n2加优化的做法,即选取每一个区间往前数进行累加得到答案,但是设置了一个最大左节点,所有右节点小于最大左节点的区间不予考虑。
问题2:我并没有考虑染色的不同,所有能够达成相加条件的直接加上,不同于其他给的dp要分01
但是我过了
这就很怪
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e6+5;
int T,n,m,flag,a[N],b[N],d[M];
long long ans,cot;
struct color{
	int l,r;
	long long num,sum;
}c[N]; 

bool cmp(color x,color y)
{
	return x.r<y.r;
}

int main()
{
	//freopen("color2.in","r",stdin);
	//freopen("color.out","w",stdout);
	cin>>T;
	while(T--)
	{
		cin>>n;
		memset(d,0,sizeof(d));
		ans=m=flag=cot=0;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			if(a[i]==a[i-1])
			{
				cot+=a[i];
				continue;
			}
			b[++m]=a[i];
			if(d[b[m]]>0)
			{
				c[++flag].l=d[b[m]];
				c[flag].r=m;
				c[flag].num=c[flag].sum=b[m];
			}
			d[b[m]]=m;
		}
		sort(c+1,c+1+flag,cmp);
		for(int i=1;i<=flag;i++)
		{
			for(int j=i-1,lm=0;j>0;j--)
			{
				if(c[j].r<lm)
					break;
				if(c[j].r<=c[i].l+1)
				{
					c[i].sum=max(c[j].sum+c[i].num,c[i].sum);
					lm=max(lm,c[j].l);
				}
			}
			ans=max(c[i].sum,ans);
		}
		cout<<ans+cot<<endl;
	}
	return 0;
}


回复

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

正在加载回复...