問題分析：

? ? 1.數(shù)據(jù)存儲：二維數(shù)組data[maxn][maxn]存儲樹塔數(shù)據(jù)，dp[maxn][maxn]用來存儲從某點(diǎn)出發(fā)的各個路徑中的最優(yōu)值

? ? 2.分析思路：樹塔樹塔問題自頂向下分析，自底向上計(jì)算。首先對倒數(shù)第二層的數(shù)據(jù)按照自頂向下的分析方法，兩兩結(jié)合選出最優(yōu)解，然后再自頂向上逐層決策，然后逐層遞推求出最終結(jié)果。

? ? 得出動態(tài)方程：dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]，最后的結(jié)果保存在dp[0][0]中。?
對于上面的數(shù)塔，我們的data數(shù)組如下：（圖轉(zhuǎn)自?https://blog.csdn.net/T_27080901/article/details/45801201）

? ?

? ? dp數(shù)組狀態(tài)如下：

? ? ? ?

不考慮路徑輸出源碼如下：

#include<iostream> #include<algorithm> using namespace std;const int maxn = 101; int n; int data[maxn][maxn]; int dp[maxn][maxn];int main() {int kase,i,j;cin>>kase;while(kase--){cin>>n;for(i=0;i<n;i++){for(j=0;j<=i;j++){cin>>data[i][j];if(i==n-1)dp[i][j]=data[i][j]; }}for(i=n-2;i>=0;i--)for(j=0;j<=i;j++) //j的限制出錯(不是j<i,而是j<=i),導(dǎo)致輸出dp[0][0]為0 //dp[i][j] = dp[i+1][j]+dp[i+1][j+1]; //最初無腦寫的動態(tài)方程dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+data[i][j];cout<<dp[0][0]<<endl;}return 0; }

? ? 3.（額外考慮下）路徑輸出

? ? ?1.利用遞歸函數(shù)打印

void print_ans(int i,int j) {cout<<data[i][j];if(i<n-1) cout<<"-->";if((dp[i][j]-data[i][j])==dp[i+1][j+1]) j++;if(i>=n-1) return;print_ans(i+1,j); }

? ? ?2.邊自底向上計(jì)算邊記錄所做的決策

#include<iostream> #include<algorithm> using namespace std;const int maxn = 101; int data[maxn][maxn]; int dp[maxn][maxn]; int path[maxn][maxn]; //初始化為0,0表示往左走，1表示往右走； //int p[maxn]; //記錄第i層的決策//后來發(fā)現(xiàn)這個記錄方法不行， 因?yàn)閜會被覆蓋 int main() {int kase,n,i,j;cin>>kase;while(kase--){cin>>n;for(i=0;i<n;i++){for(j=0;j<=i;j++){cin>>data[i][j];if(i==n-1)dp[i][j]=data[i][j]; }}for(i=n-2;i>=0;i--)for(j=0;j<=i;j++) if(dp[i+1][j]>dp[i+1][j+1]) //詳細(xì)的決策步驟，邊決策計(jì)算，邊記錄路徑{dp[i][j] = dp[i+1][j]+data[i][j];//p[i]=j;}else{dp[i][j] = dp[i+1][j+1]+data[i][j];path[i][j]=1;//p[i]=j+1;}cout<<dp[0][0]<<endl;j=0;for(i=0;i<=n-1;i++){cout<<data[i][j];j = j+path[i][j];if(i<n-1) cout<<"-->"; }/*for(i=0;i<=n-1;i++){cout<<data[i][p[i]];if(i<n-1) cout<<"-->"; }*/}return 0; }

運(yùn)行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的HDU---2084树塔的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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