6666666
2023-07-26 18:47:08
发布于:广东
12阅读
0回复
0点赞
// WonderGuIRL
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <algorithm>
#include <cstring>
#define int long long
#define enter() putchar(10)
#define debug(c,que) cerr<<#c<<" = "<<c<<que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;
#define speed_up() cin.tie(0),cout.tie(0)
#define endl "\n"
#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);
#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);
#define mst(a,k) memset(a,k,sizeof(a))
namespace Newstd
{
inline int read()
{
int x=0,k=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
{
k=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*k;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
}
using namespace Newstd;
using namespace std;
const int INF=0x3f3f3f3f3f3f3f3f;
const int ma=500005;
int a[ma],b[ma];
int dp[2][ma];
int n,sum;
#undef int
int main(void)
{
#define int long long
n=read();
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
for(register int i=1;i<n;i++)
{
b[i]=a[i+1]-a[i];
}
sort(b+1,b+n);
for(register int i=1;i<n;i++)
{
sum+=b[i]*i;
}
mst(dp[0],0x3f);
dp[0][0]=0;
int now(0),idx(0);
for(register int i=1;i<n;i++)
{
if(b[i]==0)
{
continue;
}
idx^=1ll;
mst(dp[idx],0x3f);
now+=b[i];
for(register int j=0;j<=sum;j++)
{
if(j-i*b[i]>=0)
{
dp[idx][j]=min(dp[idx][j],dp[idx^1ll][j-i*b[i]]+i*b[i]*b[i]+2*b[i]*(j-i*b[i]));
}
if(j-now>=0)
{
dp[idx][j]=min(dp[idx][j],dp[idx^1ll][j-now]+now*now);
}
}
}
int ans=INF;
for(register int i=0;i<=sum;i++)
{
if(dp[idx][i]<INF)
{
ans=min(ans,n*dp[idx][i]-i*i);
}
}
printf("%lld\n",ans);
return 0;
}
这里空空如也
有帮助,赞一个