卡死了,乌鱼
2023-07-28 20:28:01
发布于:江苏
#include <bits/stdc++.h>
#define int long long
using namespace std;
int tf = 0x3f3f3f3f3f3f3f3f;
int bz() {
int x=0,f=1;
char c;
while((c=getchar())<'0' || c>'9') {
if(c=='-') f=-1;
}
while(c>='0' && c<='9') {
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
int n,z,a[1111],b[1111],s[11111],dp[2][1111111];
void zzz(int &x,int y) {
x=min(x,y);
}
signed main() {
n=bz();
for(int i=1; i<=n; i++) a[i]=bz();
for(int i=1; i<n; i++) b[i]=a[i+1]-a[i];
sort(b+1,b+n);
for(int i=1; i<n; i++) s[i]=s[i-1]+b[i];
for(z=1; z<n && b[z]==0; z++);
memset(dp,0x3f,sizeof dp);
dp[(z-1)&1][0]=0;
for(int i=z; i<n; i++) {
int w=i&1;
for(int j=0; j<=a[n]*n; j++) dp[w][j]=tf;
for(int j=0; j<=a[n]n; j++) if(dp[w^1][j]<tf) {
zzz(dp[w][j+b[i]i],dp[w^1][j]
+2jb[i]+b[i]*b[i]*i);
zzz(dp[w][j+s[i]],dp[w^1][j]+s[i]s[i]);
}
}
int ans=tf;
for(int j=0; j<=a[n]n; j++) if(dp[(n-1)&1][j]<tf)
zzz(ans,ndp[(n-1)&1][j]-jj);
printf("%lld\n",ans);
}
这里空空如也
有帮助,赞一个