题解(法兰西加缩进加修bug版)
2023-07-15 18:55:12
发布于:浙江
86阅读
0回复
0点赞
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 10005;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
int read(){
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[M],b[M],s[M],dp[2][M*55];
void upd(int &x,int y) {
x=min(x,y);
}
signed main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
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]=inf;
for(int j=0;j<=a[n]*n;j++)
if(dp[w^1][j]<inf){
//head
upd(dp[w][j+b[i]*i],dp[w^1][j]+2*j*b[i]+b[i]*b[i]*i);
//tail
upd(dp[w][j+s[i]],dp[w^1][j]+s[i]*s[i]);
}
}int ans=inf;
for(int j=0;j<=a[n]*n;j++)
if(dp[(n-1)&1][j]<inf)
upd(ans,n*dp[(n-1)&1][j]-j*j);
printf("%lld\n",ans);
}
全部评论 1
nb
2024-05-15 来自 浙江
0
有帮助,赞一个