原題傳送門(mén)

思路

---

本題難度本為入門(mén)難度,因?yàn)樗臄?shù)據(jù)很小,用O（n²）的暴力算法就可以AC,但是,作為一個(gè)對(duì)于認(rèn)為自己水題過(guò)多而感到羞愧的OIer,我決定用O（n）的算法來(lái)做這道題.

我不打算用前綴和（其實(shí)就是不會(huì)），用前綴和也可以做出O（n）的時(shí)間復(fù)雜度，但是很復(fù)雜，而且常數(shù)因子還比我接下來(lái)要介紹的算法的常數(shù)因子大，所以，我自認(rèn)為我的這個(gè)算法是洛谷全站最好的（我翻了題解）.

思想:貪心&動(dòng)態(tài)規(guī)劃

復(fù)雜度:時(shí)間復(fù)雜度O(n);空間復(fù)雜度O(n);

如果a[n]<a[m+1],那么a[n]~a[m]區(qū)間的和一定小于a[n+1]~a[m+1]區(qū)間的和.
而a[n+1]~a[m+1]區(qū)間的和減a[n]~a[m]區(qū)間的和就等于a[m+1]-a[n].
則用dp[m+1]表示a[m+1]-a[n],那么a[n+2]~a[m+2]區(qū)間的和減a[n]~a[m]區(qū)間的和就等于a[m+1]-a[n]+a[m+2]-a[n+1]也就是b[m+1]+a[m+2]-a[n+1].而他的值又可以用dp[m+2]表示
所以得到dp[m+1]到dp[m+2]的]狀態(tài)轉(zhuǎn)移方程為:dp[m+2]=dp[m+1]+a[m+2]-a[n+1].
所以dp[m+i-1]到dp[m+i]的狀態(tài)轉(zhuǎn)移方程為dp[i+m]=dp[i+m-1]+a[i+m]-a[i]

另外,若a[1]~a[m]就是最小的范圍或者n=m,則程序會(huì)出現(xiàn)錯(cuò)誤,需要特判:

if(dp[no]>0||n==m)//特判no=m;

剩下的就很簡(jiǎn)單了,直接上代碼.

Code

---

#include <iostream> #include <queue> using namespace std;long long n,m,gkmin=99999999,ans,no;//我就是喜歡把gkmin設(shè)的大一點(diǎn),你咬我啊 long long a[3002]; long long dp[3002];int main() {cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-m;i++){dp[i+m]=dp[i+m-1]+a[i+m]-a[i];//狀態(tài)轉(zhuǎn)移if(gkmin>dp[i+m])gkmin=dp[i+m],no=i+m;}if(dp[no]>0||n==m)//特判no=m;for(int i=no;i>no-m;i--)ans+=a[i];cout<<ans;return 0; }

后記

為了裝逼敲一個(gè)高性能代碼,我足足提交了20次左右,才AC.好吧,我承認(rèn)是我自己在折磨我自己QAQ.
另外,此算法仍存在改進(jìn)空間,可以用遞歸的迭代法代替動(dòng)態(tài)規(guī)劃的龐大dp數(shù)組,從而將空間復(fù)雜度降為O(1),但因?yàn)槲覒?#xff0c;所以有興趣的可以自行改進(jìn).

轉(zhuǎn)載于:https://www.cnblogs.com/gongdakai/p/11031577.html

總結(jié)

以上是生活随笔為你收集整理的【动态规划】爱与愁的心痛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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