這個系列主要談一談關(guān)于DP的優(yōu)化肚吏，所有題目均為平時刷題所遇到的方妖，如果涉及到DP優(yōu)化相關(guān)的技巧我就會在這里記錄下來。今天這個題目講的是通過改變DP順序來進(jìn)行優(yōu)化的一種方法罚攀。
合唱
時間限制：2秒
空間限制：131072K
描述
小Q和牛博士合唱一首歌曲,這首歌曲由n個音調(diào)組成,每個音調(diào)由一個正整數(shù)表示党觅。
對于每個音調(diào)要么由小Q演唱要么由牛博士演唱,對于一系列音調(diào)演唱的難度等于所有相鄰音調(diào)變化幅度之和, 例如一個音調(diào)序列是8, 8, 13, 12, 那么它的難度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示絕對值)。
現(xiàn)在要對把這n個音調(diào)分配給小Q或牛博士,讓他們演唱的難度之和最小,請你算算最小的難度和是多少斋泄。
如樣例所示: 小Q選擇演唱{5, 6}難度為1, 牛博士選擇演唱{1, 2, 1}難度為2,難度之和為3,這一個是最小難度和的方案了杯瞻。
輸入
輸入包括兩行,第一行一個正整數(shù)n(1 ≤ n ≤ 2000) 第二行n個整數(shù)v[i](1 ≤ v[i] ≤ 10^6), 表示每個音調(diào)。
輸出
輸出一個整數(shù),表示小Q和牛博士演唱最小的難度和是多少炫掐。
樣例輸入
5
1 5 6 2 1
樣例輸出
3
分析
由于每個音要么由牛博士演唱魁莉，要么由小Q演唱，所以總的方案數(shù)有2^N次方種可能募胃，無法直接枚舉旗唁。容易發(fā)現(xiàn)枚舉過程中存在大量重復(fù)計算，因此考慮使用動態(tài)規(guī)劃求解痹束。
不妨設(shè)f[i][j]（其中i>j）代表兩人演唱的最后一個音分別為i和j時检疫，最小的難度和。同時祷嘶，我們假設(shè)s[i][j]代表連續(xù)演唱i~j所有的音所產(chǎn)生的難度和屎媳，這個s[i][j]可以事先預(yù)處理得到夺溢。
那么可以得到:
這個方程最麻煩的地方在于需要枚舉這個k，如果每次求f[i][j]都去枚舉k的話烛谊，復(fù)雜度就退化成了N^3 企垦。首先看一個N^3的代碼：
void dp()
{
int i,j,k;
memset(f,0x3f,sizeof(f));
mem(s);
f[0][0]=0;
for(i=2;i<=n;i++) s[i]=s[i-1]+abs(a[i]-a[i-1]);
for(i=1;i<=n;i++)
{
f[i][0]=s[i];
for(j=1;j<i;j++)
for(k=0;k<j;k++)
if(k) f[i][j]=min(f[i][j],f[j][k]+s[i]-s[j+1]+abs(a[k]-a[j+1]));
else f[i][j]=min(f[i][j],f[j][k]+s[i]-s[j+1]);
}
int ans = 0x3f3f3f3f;
for(i=1;i<=n;i++) ans=min(ans,f[n][i]);
printf("%d\n",ans);
}
要避免這種情況其實(shí)很簡單，方程不需要改晒来，只需要更改一下求解的順序即可钞诡。首先觀察一下上述的公式，
由于在求f[i][j]時湃崩，i,j可以看做是已知數(shù)荧降，因此，可以把s[i][j]從min()中提出來攒读，變成
沒錯朵诫，提出來之后，min()內(nèi)的部分只和j,k有關(guān)薄扁，與i無關(guān)剪返。因此，在計算任意的f[x][j]時邓梅，min()部分的值實(shí)際上是完全相同的脱盲，這部分只需要j確定，就能在o(n)的時間內(nèi)算出來日缨，而算出來之后钱反，計算所有的f[x][j]，都只需要o(1)的時間匣距。
調(diào)整后的代碼為：
void dp()
{
int i,j,k;
memset(f,0x3f,sizeof(f));
mem(s);
f[0][0]=0;
for(i=2;i<=n;i++) s[i]=s[i-1]+abs(a[i]-a[i-1]);
for(i=1;i<=n;i++) f[i][0]=s[i];
for(j=1;j<n;j++)//f[i][j] =s[i]-s[j+1]+ G;
{
int G = 0x3f3f3f3f;
for(k=0;k<j;k++)
if(k) G=min(G,f[j][k]+abs(a[k]-a[j+1]));
else G=min(G,f[j][k]);
for(i=j+1;i<=n;i++)
f[i][j]=min(f[i][j],s[i]-s[j+1]+G);
}
int ans = 0x3f3f3f3f;
for(i=1;i<=n;i++) ans=min(ans,f[n][i]);
printf("%d\n",ans);
}
