2018-3-22

因?yàn)闆]有會(huì)員，所以并不知道寫的對(duì)不對(duì)…

問(wèn)題描述
　　A城市有一個(gè)巨大的圓形廣場(chǎng)，為了綠化環(huán)境和凈化空氣，市政府決定沿圓形廣場(chǎng)外圈種一圈樹。園林部門 得到指令后，初步規(guī)劃出n個(gè)種樹的位置，順時(shí)針編號(hào)1到n。并且每個(gè)位置都有一個(gè)美觀度Ai，如果在這里種樹就可以得到這Ai的美觀度。但由于A城市土壤 肥力欠佳，兩棵樹決不能種在相鄰的位置（i號(hào)位置和i+1號(hào)位置叫相鄰位置。值得注意的是1號(hào)和n號(hào)也算相鄰位置！）。
　　最終市政府給園林部門提供了m棵樹苗并要求全部種上，請(qǐng)你幫忙設(shè)計(jì)種樹方案使得美觀度總和最大。如果無(wú)法將m棵樹苗全部種上，給出無(wú)解信息。
輸入格式
　　輸入的第一行包含兩個(gè)正整數(shù)n、m。
　　第二行n個(gè)整數(shù)Ai。
輸出格式
　　輸出一個(gè)整數(shù)，表示最佳植樹方案可以得到的美觀度。如果無(wú)解輸出“Error!”，不包含引號(hào)。
樣例輸入
7 3
1 2 3 4 5 6 7
樣例輸出
15
樣例輸入
7 4
1 2 3 4 5 6 7
樣例輸出
Error!

法一：遞歸

這個(gè)題目本身可能要求我們使用遞歸求解，因?yàn)榻o我們的數(shù)據(jù)并不是很大，step表示當(dāng)前來(lái)到了第幾個(gè)花壇，sum表示當(dāng)前的美觀度，num表示當(dāng)前種的樹的數(shù)目。用f數(shù)組標(biāo)記當(dāng)前step位置是否種樹，目的是為了使相鄰兩個(gè)不同時(shí)種樹且頭和尾不同時(shí)種樹。

#include<iostream> #include<cstring> using namespace std;const int N = 30; bool f[N+1]; int a[N+1]; int m,n,res;void dfs(int step,int sum,int num){if (num>m) return ;if (step==n){if ((!f[0]||!f[n-1])&&num==m){res=max(res,sum); }return ;}if (step==0){dfs(step+1,sum,num);f[step]=true;dfs(step+1,sum+a[step],num+1);f[step]=false;return ;}if (!f[step-1]){f[step]=true;dfs(step+1,sum+a[step],num+1);f[step]=false;}dfs(step+1,sum,num); }int main(){while (cin>>n>>m){for (int i=0;i<n;i++){cin>>a[i]; }if (m>n/2) {cout<<"Error!"<<endl;continue;}res=0;dfs(0,0,0);cout<<res<<endl;} return 0; }

如果說(shuō)m大于n/2的話，無(wú)法保證相鄰兩個(gè)不同時(shí)種樹，輸出Error！

法二：動(dòng)態(tài)規(guī)劃
（1）如果說(shuō)沒有 ” 每相鄰兩個(gè)不能同時(shí)種 ” 和 ” 環(huán)形 “這兩個(gè)條件的話，那么就等同于01背包問(wèn)題，也就是說(shuō)在n個(gè)物品中選擇m個(gè)所能獲得的最大的價(jià)值。
（2）如果說(shuō)加了 ” 每相鄰兩個(gè)不能同時(shí)種 ” 這個(gè)條件的話，也就是說(shuō)我們要是選擇某個(gè)商品的話，我們就得讓它前一個(gè)不選即可。
（3）如果說(shuō)再加上 “環(huán)形” 這個(gè)條件的話，那么我們的第0個(gè)和第n-1個(gè)不能同時(shí)選，在遞歸方法中我們是使用f數(shù)組來(lái)標(biāo)記的，這里我們就等同于在0~n-2和1~n-1中選擇最大值即可。
用dp[i][j]表示前i個(gè)坑，當(dāng)前已經(jīng)種了j棵樹所能獲得的最大的美觀度，那么如果說(shuō)第i個(gè)坑我們選擇種的話，那么等同于前i-2個(gè)坑種j-1棵樹所能獲得的最大美觀度，如果說(shuō)我們不種的話，那么就等同于前i-1個(gè)坑種j-1棵樹所能獲得的最大美觀度，我們需要求解0~n-2和1~n-1然后選擇最大值。

#include<iostream> #include<cstring> using namespace std;const int N = 30; int dp[N+1][N+1],v[N+1]; int m,n;int main(){while (cin>>n>>m){for (int i=0;i<n;i++){cin>>v[i];}if (m>n/2) {cout<<"Error!"<<endl;continue;}memset(dp,0,sizeof(dp));int r1,r2;dp[0][1]=v[0];dp[1][1]=max(v[0],v[1]);for (int i=2;i<n-1;i++){for (int j=1;j<=m;j++){dp[i][j]=max(dp[i-2][j-1]+v[i],dp[i-1][j]);}}r1=dp[n-2][m];memset(dp,0,sizeof(dp));dp[1][1]=v[1];dp[2][1]=max(v[1],v[2]);for (int i=3;i<n;i++){for (int j=1;j<=m;j++){dp[i][j]=max(dp[i-2][j-1]+v[i],dp[i-1][j]);}}r2=dp[n-1][m];cout<<max(r1,r2)<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯-算法提高-种树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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