社区讨论

求帮忙看看这个疑似平方的状物是怎么过的

P14567【MX-S12-T2】区间参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mia0wret
此快照首次捕获于
2025/11/22 16:24
3 个月前
此快照最后确认于
2025/11/22 17:35
3 个月前
查看原帖
最暴力的暴力了,只加了一个判断(就是当前颜色如果之前已经计算过了就不算了,有注释的那两行)。加了之后 2010020\rightarrow 100
CPP
#include<iostream>
#include<cstdio>
#define N 1000010
#define int long long
using namespace std;
int n,c[N],v[N],f[N],cnt0[N],cnt[N],flag,calc[N];
int sum,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>c[i],cnt0[c[i]]++;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=n;i++)
        cin>>f[i],ans+=v[i]*c[i];
    for(int i=1;i<=n;i++){
        if(calc[c[i]])continue;//这里
        calc[c[i]]=1;//还有这里
        for(int j=1;j<=n;j++)
            cnt[j]=0;
        sum=0;
        cnt[c[i]]++;
        flag=n-1;
        if(cnt[c[i]]==cnt0[c[i]])flag++;
        sum+=v[i]*f[1];
        for(int j=i+1;j<=n&&flag!=n;j++){
            if(!cnt[c[j]])flag--;
            cnt[c[j]]++;
            if(cnt[c[j]]==cnt0[c[j]])flag++;
            sum+=v[j]*f[j-i+1];
        }
        if(flag==n)ans=min(ans,sum);
    }
    cout<<ans;
    return 0;
}

回复

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

正在加载回复...