Cow Pinball

链接：https://ac.nowcoder.com/acm/contest/1081/F
来源：牛客网
 

题目描述

The cows are playing that cool Japanese 'pinball' game called Pachinko. You've probably seen it, you drop a ball in the top and it hits nails on the way down, veering just a little left or right, until the ball comes out the bottom.
This pachinko game is special: the ball always hits the top nail of the R rows of nails (1 <= R <= 25) and then will hit either the right or left nail underneath that. From there, the ball can hit the next nail that's just a bit lower and to the left or right of the second nail, and so on. The ball never veers too far (i.e., more than 1/2 nail away) from the nail it just hit.
This game also has scoring that's unique: you get points XijX_{ij}Xij​ (0 <= XijX_{ij}Xij​ <= 3,000) for each little nail you hit on the way down. The cows want to maximize their score on this machine. What is the best score they can achieve?

Here's an example triangle and a good route:

                    7                        *7

                  3   8                    *3   8

                8   1   0                *8   1   0

              2   7   4   4             2  *7   4   4

            4   5   2   6   5         4  *5   2   6   5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. It's not possible to go from 7 to 8 to 8 -- the 8 on the third row is too far away.

输入描述:

* Line 1: A single integer: R
* Lines 2..R+1: Line i+1 contains i space-separated integers that compose the scores of row R of the pachinko machine: Xi1,Xi2,...X_{i1},
        X_{i2}, ...Xi1​,Xi2​,...

输出描述:

* Line 1: A single integer that is the maximum achievable score.

示例1

输入

复制

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出

复制

30

说明

No other achievable sum is higher.

 

思路：深搜（dfs），搜索出一条路径元素和最大的路径，记录其路径元素之和

 

代码：

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int num[26][26], r, ans = 0, mx = 0;    //ans当前路径上元素之和，mx为当前所有路径上元素之和的最大值
bool book[26][26];
//int sl[26];               //记录路径
int next1[2]={0,1};

void dfs(int x, int y)
{
    if(x == r){
        mx = max(mx, ans);
//        查案路径
//        for(int i = 1; i < r; i++)
//            printf("%d ", sl[i]);
//        printf("\n");
    }


    for(int i = 0; i < 2; i++){
        int tx = x + 1;         //只能下方和左下方的钉子
        int ty = y + next1[i];
        if(book[tx][ty] == 0 && tx <= r && ty <= r)
        {
            book[tx][ty] = 1;
            ans += num[tx][ty];
//            sl[tx] = num[tx][ty];
            dfs(tx, ty);
            ans -= num[tx][ty];
            book[tx][ty] = 0;
        }
    }

}

int main()
{
    scanf("%d", &r);
    for(int i =0; i < r; i++){
        for(int j = 0; j <= i; j++)
            scanf("%d", &num[i][j]);
    }

    dfs(0, 0);
    printf("%d\n", mx + num[0][0]);

    return 0;
}