2018-4-15

1.石子合并問題
1）設有N堆沙子排成一排，其編號為1,2,3,…,N(N<=100)。每堆沙子有一定的數(shù)量?，F(xiàn)要將N堆沙子并成為一堆。歸并的過程每次將任意兩堆沙子堆成一堆（每次合并花費的代價為當前兩堆沙子的總數(shù)量），這樣經(jīng)過N-1次歸并后成為一堆，歸并的總代價為每次合并花費的代價和。找出一種合理的歸并方法，使總的代價最小。

我們可以使用貪心算法，每次只合并兩個數(shù)量最小的沙子，所得到的結果就是最優(yōu)解了。

其實這就是哈夫曼編碼的變形。

每一次都要進行排序，雖然有點智障，但是還是寫了…（注釋的地方），
我的想法是每次將合并過后的值插入到它合適的位置，使得剩下的還是有序的即可。

#include<iostream> #include<algorithm> using namespace std;const int N = 100; int x[N+1]; int n;int main(){int i,j;while (cin>>n){int sum=0;for (i=0;i<n;i++){cin>>x[i];}sort(x,x+n);// for (i=1;i<n;i++){// sum+=x[i]+x[i-1];// x[i]=x[i]+x[i-1];// sort(x+i,x+n);// }for (i=1;i<n;i++){int tmp=x[i]+x[i-1];sum+=tmp;j=i+1;while (tmp>x[j]&&j<n){x[j-1]=x[j];j++;}x[j-1]=tmp;}cout<<sum<<endl;}return 0; }

2）倘若我們每次只能合并相鄰的兩個石子呢？
貪心這個時候就不可以了，因為我們無法保證全局最優(yōu)，雖然不對，但是我還是寫了…

#include<iostream> #include<vector> #define inf 0x3f3f3f3f using namespace std;int n;int main(){vector<int>vec;while (cin>>n){int a;for (int i=0;i<n;i++){cin>>a;vec.push_back(a);}int cnt=0;for (int i=0;i<n-1;i++){int tmp=inf,k=0;for (int j=1;j<vec.size();j++){if (vec[j]+vec[j-1]<tmp){tmp=vec[j]+vec[j-1];k=j;}}cnt+=tmp;vec.erase(vec.begin()+k);vec.erase(vec.begin()+k-1);vec.insert(vec.begin()+k-1,tmp);} cout<<cnt<<endl;}return 0; }

其實正確的解法應該是用動態(tài)規(guī)劃求解：

#include<iostream> using namespace std;const int N = 1000; int x[N+1],dp[N+1][N+1],s[N+1]; int n;int main(){while (cin>>n){for (int i=1;i<=n;i++){cin>>x[i];s[i]=s[i-1]+x[i];}for (int l=2;l<=n;l++){for (int i=1;i<=n-l+1;i++){int j=i+l-1;dp[i][j]=N;for (int k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])+s[j]-s[i]+x[i];}}} // for (int i=1;i<=n;i++){ // for (int j=1;j<=n;j++){ // cout<<dp[i][j]<<" "; // } // cout<<endl; // }cout<<dp[1][n]<<endl;}return 0; }

3）其實最終的題目應該是我們的這個沙子堆是環(huán)形的！

其實對于環(huán)形問題我們之前有過涉及，就是在直線后面再補充那么多就可以了！就是與USACO里面的那個項鏈問題差不多！

#include<iostream> using namespace std;const int N = 2000; int x[N+1],dp[N+1][N+1],s[N+1]; int n;int main(){while (cin>>n){for (int i=1;i<=n;i++){cin>>x[i];s[i]=s[i-1]+x[i];}for (int i=1;i<=n;i++){x[i+n]=x[i];s[i+n]=s[i+n-1]+x[i];}for (int l=2;l<=n;l++){ //最多還是合并 n 堆沙石子 for (int i=1;i<=2*n-l+1;i++){int j=i+l-1;dp[i][j]=N;for (int k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}dp[i][j]+=s[j]-s[i]+x[i];}}int res=N;for (int i=1;i<=n;i++){res=min(res,dp[i][i+n-1]);} cout<<res<<endl;}return 0; }

2.整數(shù)劃分問題
自行車選手在訓練時，需要圍繞著場地騎行N圈。給了使得訓練有效，可以一次把N全部騎完，
也可以分成若干次完成，但每次都比上一次騎的圈數(shù)要多，那么完成一次訓練即騎完N圈，
有多種訓練方式

樣例輸入
6

樣例輸出
4

//例如，當 N = 6 時，有以下四種訓練方案：
6
1 2 3
1 5
2 4

這個題目其實就是一個整數(shù)劃分問題，整數(shù)劃分又分為好多種：
1）將n劃分成若干正整數(shù)之和的劃分數(shù)
其實這是一個方蘋果的問題，假設f(n,m)表示將n個蘋果放在m個籃子里面，那么我們一共有兩種情況：如果n>m的話，我們一定會有空的籃子，也就是等同于f(m,m)，反之n

#include<iostream> using namespace std;int n,cnt;void dfs(int sum,int pre){if (sum>n) return ;if (sum==n){cnt++;return ;}for (int i=pre;i<=n;i++){dfs(sum+i,i+1);} }int main(){while (cin>>n){cnt=0;dfs(0,1);cout<<cnt<<endl;}return 0; }

實際上應該是用動態(tài)規(guī)劃問題…

3.最長不下降子序列問題
若干人排成一行，且身高分別為b1，b2，…，bn。準備從中選出一組滿足身高不降的人組成一隊。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。
有13<16<38<44<63 長度為5的不下降子序列。
但經(jīng)過觀察，實際還有7<9<16<18<19<21<22<63 長度為8的不下降子序列。
給出最長隊列的長度。

【輸入格式】

第一行為n，表示n(n≤100000)個數(shù)。第二行為n個數(shù)的值。

【輸出格式】

一個整數(shù)。

【輸入樣例】

4

1 3 1 2

【輸出樣例】

2

簡單的動態(tài)規(guī)劃問題：

#include<iostream> using namespace std;const int N = 100000; int x[N+1],dp[N+1]; int n;int main(){while (cin>>n){for (int i=1;i<=n;i++){cin>>x[i];}for (int i=1;i<=n;i++){dp[i]=1;for (int j=1;j<i;j++){if (x[j]<=x[i]){dp[i]=max(dp[j]+1,dp[i]);}}}int res=0;for (int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res<<endl;}return 0; }

4.最長不下降子序列的升級問題
為了外來導彈襲擊，最新的導彈攔截系統(tǒng)已經(jīng)研制好了.但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。
某天，雷達捕捉到了導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈和如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

6（最多能攔截的導彈數(shù)）

2（要攔截所有導彈最少要配備的系統(tǒng)數(shù)）

#include<iostream> using namespace std;const int N = 100000; int x[N+1],dp[N+1]; int n;int main(){int i=0;while (cin>>x[i]){i++;if (getchar()=='\n') break;}n=i;for (int i=1;i<=n;i++){dp[i]=1;for (int j=1;j<i;j++){if (x[j]>=x[i]){dp[i]=max(dp[j]+1,dp[i]);}}}int res=0;for (int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res<<endl;for (int i=1;i<=n;i++){dp[i]=1;for (int j=1;j<i;j++){if (x[j]<=x[i]){dp[i]=max(dp[j]+1,dp[i]);}}}res=0;for (int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res<<endl;return 0; }

這里需要我們用一個結論：求…等于最長非遞增子序列。

總結

以上是生活随笔為你收集整理的ACM第一次集训 - 动态规划问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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