首页 > 其他分享 >P7962 [NOIP2021] 方差

P7962 [NOIP2021] 方差

时间:2022-11-25 13:00:44浏览次数:53  
标签:P7962 include 方差 ll 差分 while ch NOIP2021 sum

[NOIP2021] 方差

时隔一年。我又回来做这个题了。。。

我们通过观察是可以发现这里的操作实际上就是交换相邻差分,但是差分 \(c_1\) 不可被交换。

然后如果要求方差最小的话我们可以想到这个差分应该是单谷的。当然,实际上这就是一个直觉的结论。

想要证明的话可以从调整法入手,我们交换这个单谷的两个差分使其变成非单谷的状态,会发现方差一定会更大。

所以说我们把第一个差分数组固定后,剩下的差分数组从小到大排列,要么放在现有数列的最前面,要么放在最后面。

这个单谷的形态不可考察,我们有必要用 DP 来寻找最佳。

定义 \(f(i,s)\) 表示考虑了前 \(i\) 个差分数组(排序后),此时序列的 \(\sum a_i = s\) 时的最小的 \(\sum a _ i ^ 2\)。

考虑转移:

\[f (i-1,s) + \left(\sum_ {j=1} ^ {i} c_j \right) ^ 2\rightarrow f\left (i,s+ \left(\sum_ {j=1} ^ {i} c_j \right) \right ) \]

\[f(i-1,s) + (i-1)c _ i ^ 2 +2 c_i s + c _ 1 ^ 2 \rightarrow f( i , s + (i-1)c_i + c_1) \]

我们知道每次转移是 \(O(na)\) 的,那么直接从头至尾做就是 \(O( n ^ 2 a)\) 的。

考虑到 \(a\) 的范围不大,实际上 $c_i = 0 $ 的情况很多,而 \(c_i \ne 0\) 的情况至多只有 \(O(a)\) 的数量级。

而 \(c_i=0\) 都排在前面,我们提前铺开处理掉就可以了。

这样复杂度就是 \(O(na^2)\) 的,数据范围大概印证了这个方法就是相当的正解。

代码:

#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--]);
  }
}using Ehnaev::read;using Ehnaev::write;

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() {

  n=read();
  for(ll i=1;i<=n;i++) {
    a[i]=read();c[i]=a[i]-a[i-1];m=max(m,a[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;
}

标签:P7962,include,方差,ll,差分,while,ch,NOIP2021,sum
From: https://www.cnblogs.com/Apolynth/p/16924781.html

相关文章

  • P7963 [NOIP2021] 棋局
    P7963[NOIP2021]棋局给定\(n\timesm\)的棋盘,连有横纵\(2\)种无向边,有\(3\)种类型的边:只允许按照这条边走\(1\)步允许继续走边权为\(2\)的边,但不允许改变......
  • 36.数据计算--众数--方差
     #求众数importpandasaspdpd.set_option('display.unicode.east_asian_width',True)data=[[100,90,100],[100,76,76],[76,90,76]]columns=['数学','语文',......
  • 方差分析——双因素方差分析(R语言)
    双因素方差分析(Doublefactorvarianceanalysis)有两种类型:一个是无交互作用的双因素方差分析,它假定因素A和因素B的效应之间是相互独立的,不存在相互关系;另一个是有交互作......
  • 方差分析——正交表(一)(R语言)
    正交试验设计(orthogonaldesign简称正交设计(orthoplan),是利用正交表(orthogonaltable)科学地安排与分析多因素试验的方法,是最常用的试验设计之一。正交表是一种特殊的表格,内......
  • 方差分析—单因素方差分析(R语言)
    方差分析是由英国著名统计学家:R.A.Fisher推导,也叫F检验,用于多个样本间均数的比较(分析类别变量(有序变量))。当包含的因子是解释变量时,关注的重点通常会从预测转向组别差异......
  • 为什么样本方差(sample variance)的分母是 n-1?
    Standarddeviation  Bessel'scorrection贝塞尔校正  为什么样本方差(samplevariance)的分母是n-1?非常好的问题,探索这个问题的答案,不仅能更好的了解自己和......
  • R语言使用逻辑回归Logistic、单因素方差分析anova、异常点分析和可视化分类iris鸢尾花
    摘要本文将探讨Fisher和Anderson ​​鸢尾花​​数据集中呈现的三个变量之间的关系,特别是virginica和versicolor级别的因变量变量物种对预测变量花瓣长度和花瓣宽度......
  • 初中知识,平方差公式和一元二次方程
    初中知识,平方差公式和一元二次方程   平面直角坐标系表示 ......
  • slam14(2-2) 高斯分布 协方差
     1.数学期望:在概率论和统计学中,数学期望(mean)(或均值,也简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一,它反映随机变量平均取值的大小。需要......
  • 过拟合高方差,欠拟合高偏差
    过拟合是指在训练集上误差小,测试集上误差大;欠拟合是指在训练集和测试集上误差都大。过拟合解决办法:增加训练数据降低模型复杂度增加正则化参数采用集成学习欠拟合解决办法:增......