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