# P7962 [NOIP2021] 方差()-其他

## P7962 [NOIP2021] 方差()

[NOIP2021] 方差

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}

const ll N=1e6,M=1e6,inf=1e16;

ll n,m,sum,now,ans;
ll a[N+5],c[N+5],g[2][M+5];

int main() {

for(ll i=1;i<=n;i++) {
}

sort(c+2,c+n+1);

m=m*n;sum=c[1];
for(ll i=1;i<=m;i++) g[now][i]=inf;
g[now][sum]=sum*sum;

for(ll i=2;i<=n;i++) {
sum+=c[i];
if(c[i]!=0) {
for(ll j=1;j<=m;j++) {g[1-now][j]=inf;}
for(ll j=1;j<=m;j++) {
g[1-now][j+sum]=min(g[1-now][j+sum],g[now][j]+sum*sum);
g[1-now][j+c[i]*(i-1)+c[1]]=min(g[1-now][j+c[i]*(i-1)+c[1]]
,g[now][j]+(i-1)*c[i]*c[i]+2*c[i]*j+c[1]*c[1]);
}
now=1-now;
}
else {
g[now][sum*(i-1)]=inf;g[now][sum*i]=sum*sum*i;
continue;
}
// for(ll j=1;j<=m;j++) {
//   printf("Test: %lld %lld\n",j,g[now][j]);
// }
}

ans=inf;
for(ll i=1;i<=m;i++) {
// printf("Test: %lld %lld\n",i,g[now][i]);
ans=min(ans,n*g[now][i]-i*i);
}

write(ans);

return 0;
}
————————

[NOIP2021] 方差

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}

const ll N=1e6,M=1e6,inf=1e16;

ll n,m,sum,now,ans;
ll a[N+5],c[N+5],g[2][M+5];

int main() {

for(ll i=1;i<=n;i++) {
}

sort(c+2,c+n+1);

m=m*n;sum=c[1];
for(ll i=1;i<=m;i++) g[now][i]=inf;
g[now][sum]=sum*sum;

for(ll i=2;i<=n;i++) {
sum+=c[i];
if(c[i]!=0) {
for(ll j=1;j<=m;j++) {g[1-now][j]=inf;}
for(ll j=1;j<=m;j++) {
g[1-now][j+sum]=min(g[1-now][j+sum],g[now][j]+sum*sum);
g[1-now][j+c[i]*(i-1)+c[1]]=min(g[1-now][j+c[i]*(i-1)+c[1]]
,g[now][j]+(i-1)*c[i]*c[i]+2*c[i]*j+c[1]*c[1]);
}
now=1-now;
}
else {
g[now][sum*(i-1)]=inf;g[now][sum*i]=sum*sum*i;
continue;
}
// for(ll j=1;j<=m;j++) {
//   printf("Test: %lld %lld\n",j,g[now][j]);
// }
}

ans=inf;
for(ll i=1;i<=m;i++) {
// printf("Test: %lld %lld\n",i,g[now][i]);
ans=min(ans,n*g[now][i]-i*i);
}

write(ans);

return 0;
}