背包dp

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=1e5+50;

int n,a[maxn],dp[maxn],maxx,ans;

template<typename T>void inline read(T &aa){
    ll ff=1;char cc=getchar();aa=0;
    while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
    if(cc==‘-‘) ff=-1,cc=getchar();
    while(cc<=‘9‘&&cc>=‘0‘) aa=aa*10+cc-48,cc=getchar();
    aa*=ff;
}

int main(){
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    dp[1]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[1]+=a[i];
        maxx=max(maxx,a[i]);
    }
    ans=dp[1]; 
    for(int i=1;i<=maxx/2;i++)
    for(int j=2;j*i<=maxx;j++){
        int m=0;
        for(int k=1;k<=n;k++)
        m+=a[k]/(i*j);
        dp[i*j]=min(dp[i*j],dp[i]-(j-1)*m);
        ans=min(ans,dp[i*j]);
    }
    cout<<ans;
    return 0;
}