Problem statement:

问题陈述：

Given a rectangular grid of dimension 2 x N find out the maximum sum such that no two chosen numbers are adjacent, vertically, diagonally or horizontally.

给定尺寸为2 x N的矩形网格，找出最大和，以使没有两个选定的数字在垂直，对角线或水平方向上相邻。

Input:

输入：

The first line of input contains an integer T denoting the number of test cases.

输入的第一行包含一个整数T，表示测试用例的数量。

The first line of each test case is N, number of columns in a grid, grid length.

每个测试用例的第一行是N ，网格中的列数，网格长度。

Next two lines describes the 2*N grid.

接下来的两行描述2 * N网格。

Output:

输出：

Print the output for each test case in a separate line.

在单独的行中打印每个测试用例的输出。

Constraints:

限制条件：

1 <= T<= 1001 <= N<= 1000 <= elements <= 100

Example:

例：

Input:Test case: 1Grid column size: 5Grid as input:1 4 5 4 132 0 10 2 11Output:25

Explanation:

说明：

The above grid is like following where many combinations are possible within the constraints.

上面的网格就像下面这样，其中在约束内可能有许多组合。

Few have been shown below,

很少显示如下，

Since, we have got the maximum sum combination already, I am not considering the other combinations. The maximum sum possible to achieve is 25 which can be achieved from combination 2. (If you have doubt thinking about other combinations might produce better result, feel free to process other combinations too until you get exhausted)

因为我们已经有了最大的总和组合，所以我不考虑其他组合。 可以通过组合2获得的最大总和为25。(如果您怀疑其他组合可能会产生更好的结果，请随时处理其他组合，直到您精疲力尽)

So, the answer will be 25.

因此，答案将是25。

Solution approach

解决方法

This is a standard recursion problem where we are supposed to either consider one number or not consider that number.

这是一个标准的递归问题，我们应该考虑一个数字或不考虑该数字。

Say, the current element under our processing is: arr[r][c]

假设我们正在处理的当前元素是： arr [r] [c]

So, there are two choice,

因此，有两种选择

1. Select arr[r][c] as part of solution then we need to skip all of arr[r+1][c], arr[r][c+1] and arr[r+1][c+1]

   选择arr [r] [c]作为解决方案的一部分，然后我们需要跳过所有arr [r + 1] [c] ， arr [r] [c + 1]和arr [r + 1] [c + 1]

2. Don't select arr[r][c]

   不要选择arr [r] [c]

If we formulate the recursive function, then it becomes,

如果我们制定递归函数，则它变为

f(r,c)  =   maximum(arr[r][c]+f(r,c-2),arr[r][c]+f(r-1,c-2),    arr[r-1][c]+f(r,c-2),arr[r-1][c]+f(r-1,c-2),    f(arr,r,c-1,n),f(r-1,c-1));

The above recursion is generally illustrated on basis of assumption that all the indexed are valid.

通常基于所有索引均有效的假设来说明上述递归。

The above recursion will generate many overlapping sub-problems and hence we need to memorize. Below is the detailed memorization process.

上述递归将产生许多重叠的子问题，因此我们需要记住。 以下是详细的记忆过程。

In the main function,

在主要功能上

Initialize dp[3][n] with -1 which will store the computed sub-problem result.

用-1初始化dp [3] [n] ，它将存储计算出的子问题结果。

Call the recursive function, myrecur(arr,0,0,n)

调用递归函数myrecur(arr，0,0，n)

The function signature is described below,

功能签名如下所述：

Function myrecur(int arr[][],int r,int c,int n):    if(r>=2)        return 0;    if(c>=n)        return 0;        // if already computed    if(dp[r][c]!=-1)    return dp[r][c];            // check for valid index    if(r+1<2)         dp[r][c] = maximum(arr[r][c] + myrecur(arr,r,c+2,n), arr[r][c] +         myrecur(arr,r+1,c+2,n), arr[r+1][c] + myrecur(arr,r,c+2,n),        arr[r+1][c] + myrecur(arr,r+1,c+2,n), myrecur(arr,r,c+1,n),        myrecur(arr,r+1,c+1,n));        else        dp[r][c] = maximum(arr[r][c] + myrecur(arr,r,c+2,n),         arr[r][c] + myrecur(arr,r+1,c+2,n), myrecur(arr,r,c+1,n),        myrecur(arr,r+1,c+1,n),INT_MIN,INT_MIN);        end if else                return dp[r][c]  // which is the final maximum sum    End function

C++ Implementation:

C ++实现：

#include 
    
     using namespace std;int dp[3][101];int maximum(int a, int b, int c, int d, int e, int f){    return max(max(max(a, b), max(c, d)), max(e, f));}int myrecur(vector
     
      
        > arr, int r, int c, int n){    if (r >= 2)        return 0;    if (c >= n)        return 0;    if (dp[r][c] != -1)        return dp[r][c];    if (r + 1 < 2) {        dp[r][c] = maximum(arr[r][c] + myrecur(arr, r, c + 2, n), arr[r][c] + myrecur(arr, r + 1, c + 2, n),            arr[r + 1][c] + myrecur(arr, r, c + 2, n), arr[r + 1][c] + myrecur(arr, r + 1, c + 2, n),            myrecur(arr, r, c + 1, n), myrecur(arr, r + 1, c + 1, n));    }    else {        dp[r][c] = maximum(arr[r][c] + myrecur(arr, r, c + 2, n), arr[r][c] + myrecur(arr, r + 1, c + 2, n),            myrecur(arr, r, c + 1, n), myrecur(arr, r + 1, c + 1, n), INT_MIN, INT_MIN);    }    return dp[r][c];}int my(vector
       
        
          > arr, int n){    for (int i = 0; i <= n; i++) {        dp[0][i] = -1;        dp[1][i] = -1;        dp[2][i] = -1;    }    return myrecur(arr, 0, 0, n);}int main(){    int t, n, item;    cout << "Enter Number of test cases" << endl;    cin >> t;    for (int i = 0; i < t; i++) {        cout << "Enter length of the array\n";        cin >> n;        vector
         
          
            > arr; cout << "Enter the grid\n"; for (int i = 0; i < 2; i++) { vector
           
             a; for (int j = 0; j < n; j++) { cin >> item; a.push_back(item); } arr.push_back(a); } cout << "maximum sum possible is: " << my(arr, n) << endl; } return 0;}
           
          
         
        
       
      
     
    

Output:

输出：

Enter Number of test cases1Enter length of the array5Enter the grid1 4 5 4 132 0 10 2 11maximum sum possible is: 25

翻译自: