【題目描述】： ZL王國有一條母親河，沿河有N個農莊，ZL王國的農產品都是出產自這N個農莊。為了抵制黑心的農販子，這次ZL國王決定由王國統一收購，并給出了讓農戶非常滿意的價格，甚至國王還下旨運輸路費王國報銷。這N個農莊主非常高興，決定滿載貨船趕往收購點。可是王國的國庫空虛，勉強夠收購農產品，至于建臨時收購點和報銷運輸費的錢……ZL國王拿出了自己的私房錢，含淚對著你說：“萬能的IOer，請你幫我算算選擇哪些農莊建立收購點，可以讓我出最少的錢。”ZL國王遞給你一個表格，上面記錄了，相鄰農莊運輸的費用以及在不同農莊建立臨時收購點的費用。簡易題面：N個農莊（1~N）在一條線上，依次給定相鄰農莊間運輸費用和在不同農莊建立臨時收購點的費用，總費用即每個農莊前往運輸費用最少的收購點和所有收購點建立費用之和。）【輸入描述】： 第一行包含1 個正整數n。第二行包含n 個自然數，依次表示N個農莊建立收購點的代價cost。以下n-1 行每行一個整數w，依次表示在農莊i和i+1間運輸費用w。【輸出描述】： 輸出1 個整數，表示最小代價。【樣例輸入】： 8 1 3 3 8 5 5 4 4 3 1 9 9 9 8 0 【樣例輸出】： 27 【樣例說明】： 樣例中在1、2、4、5、6、7建立收購點。【時間限制、數據范圍及描述】： 時間：1s 空間：512M30%的數據：n≤10；70%的數據：n≤500；100%的數據：1≤n≤5000；0≤w,cost≤5000；本題可以設f[i]為以i為最后一個收購點的最小花費,然后狀態轉移方程就可以寫為f[i]=f[j]+W(j,k)+W(k,i) 注意:這里j為上一個收購點的位置,k為滿足dis[j][k]<dis[k][i]的最后一個k的位置. 另外,k如果枚舉的話會超時,所以還是尺取大法好.Code: #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<ctime> using namespace std; const int N=5005; int n; long long f[N],ans,cost[N],dis[N][N],sum; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&cost[i]);}for(int i=2;i<=n;i++){scanf("%lld",&dis[i-1][i]);f[i]=dis[i-1][i];}for(int i=1;i<n;i++){for(int j=i+2;j<=n;j++){f[j]+=dis[i][j]=dis[i][j-1]+dis[j-1][j];}}f[1]=cost[1];for(int i=2;i<=n;i++){long long l=0,r=f[i]-dis[1][i];for(int j=1,k=2;j<i;j++){while(dis[j][k]<dis[k][i]){l+=dis[j][k];r-=dis[k][i];k++;}if((f[j]+l+r)<f[i]){f[i]=f[j]+l+r;}l-=dis[j][j+1]*(k-(j+1));}f[i]+=cost[i];}ans=f[n];for(int i=n-1;i>=1;i--){sum+=dis[i][n];if(f[i]+sum<ans){ans=f[i]+sum;}}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11577787.html

總結

以上是生活随笔為你收集整理的UOJ #592. 投放点的选择的全部內容，希望文章能夠幫你解決所遇到的問題。

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