奇数塔问题

2023-12-25 23:43:52

问题描述

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

分析

考虑用 dp 来做。

状态:

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

状态转移方程:

  • 如果 a i , j a_{i,j} ai,j? 是偶数: d p i , j , 1 = max ? ( d p i + 1 , j , 1 , d p i + 1 , j + 1 , 1 ) + a i , j dp_{i,j,1} = \max(dp_{i+1,j,1},dp_{i+1,j+1,1})+a_{i,j} dpi,j,1?=max(dpi+1,j,1?,dpi+1,j+1,1?)+ai,j? d p i , j , 0 = max ? ( d p i + 1 , j , 0 , d p i + 1 , j + 1 , 0 ) + a i , j dp_{i,j,0} = \max(dp_{i+1,j,0},dp_{i+1,j+1,0})+a_{i,j} dpi,j,0?=max(dpi+1,j,0?,dpi+1,j+1,0?)+ai,j?
  • 如果 a i , j a_{i,j} ai,j? 是奇数: d p i , j , 1 = max ? ( d p i + 1 , j , 0 , d p i + 1 , j + 1 , 0 ) + a i , j dp_{i,j,1} = \max(dp_{i+1,j,0},dp_{i+1,j+1,0})+a_{i,j} dpi,j,1?=max(dpi+1,j,0?,dpi+1,j+1,0?)+ai,j? d p i , j , 0 = max ? ( d p i + 1 , j , 1 , d p i + 1 , j + 1 , 1 ) + a i , j dp_{i,j,0} = \max(dp_{i+1,j,1},dp_{i+1,j+1,1})+a_{i,j} dpi,j,0?=max(dpi+1,j,1?,dpi+1,j+1,1?)+ai,j?

初始状态

d p i , j , 0 = d p i , j , 1 = ∞ dp_{i,j,0}=dp_{i,j,1}=\infty dpi,j,0?=dpi,j,1?=

  • 如果 a n , i a_{n,i} an,i? 是偶数 d p n , i , 0 = a n , i , d p n , i , 1 = 0 dp_{n,i,0} = a_{n,i},dp_{n,i,1}=0 dpn,i,0?=an,i?,dpn,i,1?=0
  • 如果 a n , i a_{n,i} an,i? 是奇数 d p n , i , 1 = a n , i , d p n , i , 0 = 0 dp_{n,i,1} = a_{n,i},dp_{n,i,0}=0 dpn,i,1?=an,i?,dpn,i,0?=0

答案输出 d p 1 , 1 , 1 dp_{1,1,1} dp1,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;
}

文章来源:https://blog.csdn.net/zc2000911/article/details/135209005
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。