奇数塔问题

问题描述

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，最终答案必须在最后一行，且为奇数，问答案最大是多少？

分析

考虑用 dp 来做。

状态：

$d{p}_{i,j,0}$ 为走到点 $i,j$ 的偶数长度最大路径，$d{p}_{i,j,1}$ 为走到点 $i,j$ 的奇数长度最大路径。

状态转移方程：

• 如果 $a_{i,j}$ 是偶数：$d{p}_{i,j,1}=\max (d{p}_{i+1,j,1},d{p}_{i+1,j+1,1})+a_{i,j}$，$d{p}_{i,j,0}=\max (d{p}_{i+1,j,0},d{p}_{i+1,j+1,0})+a_{i,j}$。
• 如果 $a_{i,j}$ 是奇数：$d{p}_{i,j,1}=\max (d{p}_{i+1,j,0},d{p}_{i+1,j+1,0})+a_{i,j}$，$d{p}_{i,j,0}=\max (d{p}_{i+1,j,1},d{p}_{i+1,j+1,1})+a_{i,j}$。

初始状态

$d{p}_{i,j,0}=d{p}_{i,j,1}=\infty$。

• 如果 $a_{n,i}$ 是偶数 $d{p}_{n,i,0}=a_{n,i},d{p}_{n,i,1}=0$。
• 如果 $a_{n,i}$ 是奇数 $d{p}_{n,i,1}=a_{n,i},d{p}_{n,i,0}=0$。

答案输出 $d{p}_{1,1,1}$ 即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
int n, a[N][N], dp[N][N][2];

int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= i; j ++){
			cin >> a[i][j];
			dp[i][j][0] = dp[i][j][1] = -1e9;
		}
	}
	for(int i = 1; i <= n; i ++){
		if(a[n][i] % 2 == 0){
			dp[n][i][0] = a[n][i];
			dp[n][i][1] = 0;
		}else{
			dp[n][i][1] = a[n][i];
			dp[n][i][0] = 0;
		}
	}
	for(int i = n - 1; i >= 1; i --){
		for(int j = 1; j <= i; j ++){
			if(a[i][j] % 2 == 0){//偶数 
				dp[i][j][1] = max(dp[i + 1][j][1], dp[i + 1][j + 1][1]) + a[i][j];
				dp[i][j][0] = max(dp[i + 1][j][0], dp[i + 1][j + 1][0]) + a[i][j];
			}else{//奇数 
				dp[i][j][1] = max(dp[i + 1][j][0], dp[i + 1][j + 1][0]) + a[i][j];
				dp[i][j][0] = max(dp[i + 1][j][1], dp[i + 1][j + 1][1]) + a[i][j];
			}
		}
	}
	cout << dp[1][1][1];
	return 0;
}