題目鏈接

https://www.luogu.org/problemnew/show/P4677

分析

這道題方法跟之前題不一樣,我們相當于枚舉一個左右端點來線性擴展,同時劃分斷點進行決策

\(f[i][j]\)表示在前\(i\)個村莊中建立\(j\)個小學的最小距離總和

我們將枚舉到第\(i\)個村莊作為階段,修了\(j\)所小學作為狀態,通過枚舉斷點\(k\)來分割第\(j\)所小學與前\(j-1\)所小學

也就是說我們判斷\(f[k][j-1]\)加上將新加入的第\(j\)座小學建在后面的第\(k+1\)到第\(i\)座村莊中作出的貢獻（也就是新產生的距離,我們假設\(f[k][j-1]\)已經是最優的）是否更優,那么怎么這個貢獻怎么求呢呢?比較顯然當小學建在\([k+1,i]\)中點處產生的新距離之和最小.為了快速求我們可以先預處理出來

狀態轉移

memset(f,0x3f,sizeof(f));f[0][0]=0;for(ri i=1;i<=n;i++){//枚舉第幾座村莊 for(ri j=1;j<=min(i,m);j++){//枚舉修了多少小學 for(ri k=j-1;k<i;k++){//斷點,枚舉前j-1所小學都建在了[1,k]這個區間村莊內 f[i][j]=min(f[i][j],f[k][j-1]+dis[k+1][i]);}}}

代碼

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cctype> #include <cmath> #define ll long long #define ri register int using std::min; using std::abs; using std::max; template <class T>inline void read(T &x){x=0;int ne=0;char c;while(!isdigit(c=getchar()))ne=c=='-';x=c-48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ; } const int maxn=505; const int inf=0x7fffffff; int f[maxn][maxn],s[maxn][maxn],dis[maxn][maxn]; int n,m,pos[maxn]; /*inline int dis(int l,int r){int mid=(l+r)>>1,x=0;for(ri i=l;i<=r;i++)x+=abs(pos[i]-pos[mid]);return x; }*/ int main(){read(n),read(m);for(ri i=2;i<=n;i++){read(pos[i]);pos[i]+=pos[i-1];}for(ri i=1;i<=n;i++){for(ri j=i;j<=n;j++){s[i][j]+=s[i][j-1]+pos[j];}}for(ri l=1;l<=n;l++){for(ri r=l;r<=n;r++){int mid=(l+r)>>1;dis[l][r]+=(mid-l)*pos[mid]-s[l][mid-1];dis[l][r]+=s[mid+1][r]-(r-mid)*pos[mid];}}memset(f,0x3f,sizeof(f));f[0][0]=0;for(ri i=1;i<=n;i++){//枚舉第幾座村莊 for(ri j=1;j<=min(i,m);j++){//枚舉修了多少小學 for(ri k=j-1;k<i;k++){//斷點,枚舉前j-1所小學都建在了[1,k]這個區間村莊內 f[i][j]=min(f[i][j],f[k][j-1]+dis[k+1][i]);}}}printf("%d\n",f[n][m]);return 0; }

轉載于:https://www.cnblogs.com/Rye-Catcher/p/9648317.html

總結

以上是生活随笔為你收集整理的luogu4677山区建小学题解--区间DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。