2020.4.3 阿里巴巴 笔试题

第一题：

小强和小明是很好的朋友，有一天小强在刷题的时候遇到一一个他从来没遇到过的问题，问题是这样描述的:
给你一个长度n数组a,问数组中有多少有价值的数?规定若a_x为有价值的数，当且仅当:
x左侧存在大于a_x的数，右侧存在小于a_x的数，论左侧最小的大于a_x的数为f，右侧小于a_x的最大的数记为g: f为g的倍数。
输入描述:
输入包含两行，第1行仅一个整数n,表示数组的长度接下来一行有n个整数,表示数组a
保证全部数据: 1≤n≤10^5,1≤a_i≤10^18
输出描述:
输出仅一行，表示数组中有价值的数的个数。

测试用例：

3

4 3 2

输出1

第二题：

小强有一天想去郊区玩，但是路上会经过一片山路。山路可以看作是一个n * m (n行m列)的网格，每个网格代表一个区域。山路崎岖不平，每一个区域都有一个会消耗的体力值。小强在走山路的时候，只能从一个区域走到相邻的4个(上下左右的网格)区域中的任意一个。每到一个区域，会消耗对应的体力值。小强初始位置在第1行上方，需要去到第n行下方(可以在第1行任意区域作为起点，第n行任意区域作为终点)
小强想找种走法，使得经过山路的总体力值消耗最小。请你帮小强找到这么一条路，并输出最小的总体力值消耗。
输入描述:
第一行包含两个数字n，m,分别代表山路的行数和列数。
接下来有几行，每行m个数字。第i行j列的数字吃，代表对应位置的区域的体力值。
其中1≤n,m ≤ 1000,0< Vi,j≤1000
测试用例：

3 3

3 1 3

3 1 0

3 1 3

输出3

3 4
9 9 1 1
9 1 1 9
1 1 9 9
输出4

第二题的代码，超时了，ac60%

#include "bits/stdc++.h"
using namespace std;

int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};

int main() {
    int n, m , t;
    cin >> n >> m;
    int a[n][m];
    long long dp[n][m];
    long long res = INT_MAX;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> t;
            a[i][j] = t;
            if (i == 0) {
                q.emplace(i, j);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0) {
                dp[i][j] = a[i][j];
            } else
                dp[i][j] = INT_MAX;
        }
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == 0) {
            int tx = x + dx[0];
            int ty = y + dy[0];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) {
                dp[tx][ty] = dp[x][y] + a[tx][ty];
                q.emplace(tx, ty);
            }
        } else if (x == n - 1) {

        } else {
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) {
                    dp[tx][ty] = dp[x][y] + a[tx][ty];
                    q.emplace(tx, ty);
                }
            }
        }
    }
    for (int j = 0; j < m; ++j) {
        res = min(dp[n-1][j], res);
    }
    cout << res << endl;


    return 0;
}