DP数タワー問題
1131 ワード
最上階から下層階まで歩くことが求められ、一歩ごとに隣接するノードまでしか歩けない場合、通過するノードの数の和は最大でいくらですか?
試験例の最初の行は整数N(1<=N<=100)であり、数塔の高さを表し、次に数塔をN行の数字で表し、i行目にi個の整数があり、すべての整数が区間[0,99]内にある.Outputは、各テストインスタンスについて、出力可能な最大和であり、各インスタンスの出力が1行を占める.
Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30
DPを使わなければ、DFSを使うこともできますが、メモリを消費します.DPでやるには状態を探す必要があります.
現在i番目,j番目に進むと,現在の状態はi,jから最下層の最大ノードとなり,初期条件が最下層のdp配列が彼自身であることが容易に考えられる.
次に状態遷移を見る:i,jノードに着いて、私たちは2つの選択があります:1.左下へ行く.理論上の状態遷移方程式を右下に進むと決定される
すなわち、dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])である.しかし問題が発生し、dp[i+1]の層の状況を知らなかった.
そのため初期条件を合わせると,底から上へ行くことが考えられる.
試験例の最初の行は整数N(1<=N<=100)であり、数塔の高さを表し、次に数塔をN行の数字で表し、i行目にi個の整数があり、すべての整数が区間[0,99]内にある.Outputは、各テストインスタンスについて、出力可能な最大和であり、各インスタンスの出力が1行を占める.
Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30
DPを使わなければ、DFSを使うこともできますが、メモリを消費します.DPでやるには状態を探す必要があります.
現在i番目,j番目に進むと,現在の状態はi,jから最下層の最大ノードとなり,初期条件が最下層のdp配列が彼自身であることが容易に考えられる.
次に状態遷移を見る:i,jノードに着いて、私たちは2つの選択があります:1.左下へ行く.理論上の状態遷移方程式を右下に進むと決定される
すなわち、dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])である.しかし問題が発生し、dp[i+1]の層の状況を知らなかった.
そのため初期条件を合わせると,底から上へ行くことが考えられる.
#include
#include
#include
using namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int g[maxn][maxn];
int t;
int main()
{
scanf("%d",&t);
for(int i=0;i=0;i--)
{
for(int j=0;j<=i;j++)
{
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+g[i][j];
}
}
printf("%d",dp[0][0]);
return 0;
}