这个能用贪心做吗?
查看原帖
这个能用贪心做吗?
758273
liuletian楼主2022/7/22 23:38

这是我原本的做法,是别人教我的,请问这道题能用贪心做吗?

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N=1e4+5,K=605;
int n,a[N],cnt[K],num;
pii y[K];
int b[N],m[N],ans;

void print(){
    m[1]=a[1];
    for(int i=2;i<=n;i++)
    m[i]=m[i-1]+b[i];
    int tot=0,sum=0;
    for(int i=1;i<=n;i++)
    tot+=n*m[i]*m[i],sum+=m[i];
    ans=min(ans,tot-sum*sum);
}

void dfs(int w,int l ,int r){
    if(!w){
        for(int j=l;j<=r;j++) b[j]=0;
        print();
        return;
    }
    for(int i=0;i<=y[w].se;i++){
        for(int j=l;j<=r;j++)b[j]=y[w].fi;
        dfs(w-1,l+i,(r-y[w].se+i));
    }
}
int  main(){
    ios::sync_with_stdio(false);
    cin>>n;
    ans=2e9;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>1) cnt[a[i]-a[i-1]]++;
    }
    for(int  i=1;i<=600;i++)
    if(cnt[i]) y[++num]=mkp(i,cnt[i]);
    dfs(num,2,n);
    cout<<ans<<endl;
    return 0;
}
2022/7/22 23:38
加载中...