景觀美化

題目大意：

有n個花圃，里面有一定的泥土，可以將泥土運到別的花圃，也可以填入，也可以挖出，現(xiàn)在要改變花圃中的泥土數(shù)量，問最少花多少錢

原題：

題目描述：

農(nóng)夫約翰最近決定來美化他的花園，他需要運輸很多的泥土。花園是由N塊花圃組成的。第i塊花圃初始的時候有Ai數(shù)量的泥土。為了達到美化的目的，必須使得第i塊花圃的泥土數(shù)量Ai變成Bi。
約翰有三個選擇：第一，他可以買一個單位的泥土放進任意花圃中，代價是X；第二，他可以將一個單位的泥土從某一個花圃中除去，代價是Y；第三，他可以將第i塊花圃中的一個單位的泥土搬運到第j塊花圃中，大家是Z*|i-j|。

問題描述

請幫助約翰計算為了達到目的最小需要花費的代價。

輸入

第一行四個整數(shù)，分別是N，X，Y，Z。
接下來N行，每行兩個整數(shù)，分別表示Ai和Bi。

輸出

只有一行一個整數(shù)，表示最小的代價。

輸入樣例

4 100 200 1 1 4 2 3 3 2 4 0

輸出樣例

210

說明

數(shù)據(jù)范圍：1<=N<=100,0<=Ai,Bi<=10，0<=X,Y,Z<=1000。
說明：從第4個花圃中所有的土必須被除去，其中1個單位的土被直接除去，代價是200，剩下3個單位的土從第4個花圃到第1個花圃，

解題思路：

首先把每一塊泥土用他所在的坑表示出來，就變成了1223334444和111122233，然后題目就變成了“編輯字符距離”
設f[i][j]為原來的前i個單位泥土變成目標的前j個泥土的最小代價
所以三個操作分別是：
填入：因為當前要填入，所以填入之前要和j-1相同所以f[i][j]=f[i][j-1]+x;
挖出：因為是挖出，所以挖去一個后要和j相同所以f[i][j]=f[i-1][j]+y;
移動：就是把當前的移到目標的就行了，就是f[i][j]=f[i-1][j-1]+z×abs(a[i]-b[j])
然后求最小了

代碼：

#include<cstdio> #include<cstring> #include<iostream> #define abs(aa) ((aa)<0?-(aa):(aa))//絕對值 using namespace std; int n,x,y,z,xx,yy,an,bn,a[1005],b[1005],f[1005][1005]; int main() {scanf("%d %d %d %d",&n,&x,&y,&z);for (int i=1;i<=n;++i){scanf("%d %d",&xx,&yy);for (int j=1;j<=xx;++j)a[++an]=i;//改變表達方式for (int j=1;j<=yy;++j)b[++bn]=i;} memset(f,0x7f,sizeof(f));for (int i=0;i<=an;++i)f[i][0]=y*i;//預處理for (int i=0;i<=bn;++i)f[0][bn]=x*i;for (int i=1;i<=an;++i)for (int j=1;j<=bn;++j)f[i][j]=min(f[i-1][j-1]+z*abs(a[i]-b[j]),min(f[i][j-1]+x,f[i-1][j]+y));//DPprintf("%d",f[an][bn]); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【DP】景观美化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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