1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
#include <iostream> #include <set> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N = 100 + 5; int maze[N][N]; int dp[N][N]; bool vis[N][N]; int n; int (int x,int y) { if(dp[x][y]) return dp[x][y]; if(x>n||y>n) return 0; int ans=0; ans = max(maze[x][y] + dfs(x + 1, y), maze[x][y] + dfs(x + 1, y + 1)); dp[x][y]=ans; return dp[x][y]; } int main() { int t; cin >> t; while(t--) { memset(dp,0,sizeof dp); cin >> n; for (int i = 1; i <= n;i++) { for (int j = 1; j <= i;j++) { cin >> maze[i][j]; if(i==n) dp[i][j] = maze[i][j]; } } cout << dfs(1, 1) << endl; } }
|
近期评论