正題

題目鏈接:https://www.luogu.com.cn/problem/P7962

---

題目大意

給出一個(gè)長(zhǎng)度為$n$的序列$a$，你每次可以讓一個(gè)$a_i(1<i<n)=a_{i?1}+a_{i+1}?a_i$，求能變出的最小方差。

$1\le n\le 400,1\le a_i\le 600$或$1\le n\le 10^4,1\le a_i\le 50$

---

解題思路

民間數(shù)據(jù)過了就當(dāng)過了吧

這個(gè)式子顯然我們可以差分之后變成交換相鄰的數(shù)，讓所有的數(shù)都減去$a_1$這樣方差不變并且第一個(gè)保證為$0$，然后我們記差分?jǐn)?shù)組$b_i=a_{i+1}?a_i$，那么化一下答案的式子就是
$$n\sum _{i=1}^n{a}_i^2?{\left(\sum _{i=1}^n{a}_i\right)}^2?n\sum _{i=1}^{n?1}{\left(\sum _{j=1}^i{b}_j\right)}^2?{\left(\sum _{i=1}^{n?1}{b}_i(n?i)\right)}^2$$

這個(gè)式子乍一眼我們看不出什么，但是我們可以得到每個(gè)$b_i$對(duì)之間乘積的權(quán)重記為$f_{i,j}$，會(huì)發(fā)現(xiàn)$f_{i,j}$是按照$i/j$相互之間越接近/越接近中間而遞增的，但是依然會(huì)出現(xiàn)一些邊邊的靠近數(shù)對(duì)的情況比中間的不那么靠近數(shù)對(duì)的權(quán)重要高。

一個(gè)直觀的想法是類似于一個(gè)山谷之類的填法，打幾個(gè)表之后不難發(fā)現(xiàn)確實(shí)是從一個(gè)點(diǎn)往兩邊遞增的規(guī)律。

考慮在此基礎(chǔ)上進(jìn)行$dp$，考慮在一個(gè)填好的序列的前面/后面加上一個(gè)數(shù)字會(huì)產(chǎn)生的變化，記$ans$為原來的答案，記$L$為題目中給出的$n$（因?yàn)槟壳拔覀冞€沒有放完$n$個(gè)數(shù)字，所以此時(shí)的$n$不一樣），$x$為插入的數(shù)組。

• 插在前面：
  $$L\sum _{i=1}^{n?1}{\left(\sum _{j=1}^i{b}_j+x\right)}^2?{\left(nx+\sum _{i=1}^{n?1}{b}_i(n?i)\right)}^2$$
  $$?ans+Ln{x}^2+2Lx\sum _{i=1}^{n?1}{b}_j?2nx\sum _{i=1}^{n?1}{b}_i(n?i)?n^2{x}^2$$
• 插在后面：
  $$L?\sum _{i=1}^{n?1}{\left(\sum _{j=1}^i{b}_j\right)}^2+{\left(x+\sum _{i=1}^{n?1}{b}_i\right)}^2??{\left(x+\sum _{i=1}^{n?1}{b}_i+\sum _{i=1}^{n?1}{b}_i(n?i)\right)}^2$$
  $$?ans+L{\left(x+\sum _{i=1}^{n?1}{b}_i\right)}^2?{\left(x+\sum _{i=1}^{n?1}{b}_i\right)}^2?2\left(x+\sum _{i=1}^{n?1}{b}_i\right)\left(\sum _{i=1}^{n?1}{b}_i(n?i)\right)$$

然后會(huì)發(fā)現(xiàn)我們很難知道${\sum }_{i=1}^{n?1}{b}_i(n?i)$這個(gè)東西，所以考慮放進(jìn)$dp$數(shù)組里面維護(hù)，但是如果丟進(jìn)去維護(hù)了后面那個(gè)東西就完全沒有必要了，所以可以刪掉很多復(fù)雜的部分。

那么設(shè)$f_{i,j}$表示目前填了$i$個(gè)${\sum }_{i=1}^{n?1}{b}_i(n?i)=j$時(shí)的最小方差，然后就可以$O(1)$轉(zhuǎn)移了。

這樣的時(shí)間復(fù)雜度是$O(n^2{a}_i)$的，可以拿到$88$分，我在考場(chǎng)上就止步于此了。

現(xiàn)在來分析一下最后一個(gè)點(diǎn)$a_i\le 50$的性質(zhì)，也就是說差分?jǐn)?shù)組里面最多只有$50$個(gè)數(shù)是有值的，所以有一堆$0$，直接動(dòng)態(tài)更新$dp$枚舉的上界就過了。
時(shí)間復(fù)雜度：$O(n{a}_i\min \{a_i,n\})$

$好不容易那么接近一次正解，你卻讓我輸的那么徹底，焯！$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10,inf=1e18; ll n,L,a[N],s[N],f[2][N],ans; signed main() {scanf("%lld",&n);if(n==1)return puts("0");for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);L=n*a[n];ans=inf;for(ll i=1;i<n;i++)a[i]=a[i+1]-a[i];n--;sort(a+1,a+1+n);L=a[1];for(ll i=1;i<=n;i++)s[i]=s[i-1]+a[i];for(ll i=0;i<=L;i++)f[1][i]=inf;f[1][a[1]]=a[1]*a[1];for(ll k=2;k<=n;k++){int R=s[k]*k;for(ll i=0;i<=R;i++)f[k&1][i]=inf;for(ll i=0;i<=L;i++){if(f[~k&1][i]!=inf){f[k&1][i+a[k]*k]=min(f[k&1][i+a[k]*k],f[~k&1][i]+k*a[k]*a[k]+2ll*i*a[k]);f[k&1][i+s[k]]=min(f[k&1][i+s[k]],f[~k&1][i]+s[k]*s[k]);}}L=R;}for(ll i=0;i<=L;i++)if(f[n&1][i]!=inf)ans=min(ans,f[n&1][i]*(n+1)-i*i);printf("%lld\n",ans);return 0; } /* 10 6 19 34 35 56 63 82 82 83 99 */

總結(jié)

以上是生活随笔為你收集整理的P7962-[NOIP2021]方差【dp,差分】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。