矩阵取数游戏

C 解法, 执行用时: 92ms, 内存消耗: 1052KB, 提交时间: 2022-06-23

int *multi(int *a, int aLen, int b) {
    int *result = (int *)malloc(sizeof(int) * 10);   
    long carry = 0, v;
    for (int i = 0; i < aLen; i++) {
        v = a[i] * b + carry;
        carry = v / 1000000007;
        result[i] = v % 1000000007;
    }   
    return result;
}

int *add(int *a, int aLen, int *b, int bLen) {
    int *result = (int *)malloc(sizeof(int) * 10);
    
    long carry = 0, v;
    for (int i = 0; i < aLen; i++) {
        v = a[i] + b[i] + carry;
        carry = v / 1000000007;
        result[i] = v % 1000000007;
    }
    
    return result;
}

int *max(int *a, int aLen, int *b, int bLen) {
    for (int i = aLen - 1; i >= 0; i--) {
        if (a[i] > b[i]) {
            return a;
        } else if (a[i] < b[i]) {
            return b;
        }
    }
    
    return a;
}

int maxRow(int *matrix, int len, int **powArray) {
    int ***dp = (int ***)malloc(sizeof(int **) * (len + 1));
    for (int i = 0; i < len + 1; i++) {
        dp[i] = (int **)malloc(sizeof(int *) * (len + 1));
        for (int j = 0; j < len + 1; j++) {
            dp[i][j] = (int *)malloc(sizeof(int) * 10);
            memset(dp[i][j], 0, sizeof(int) * 10);
        }
    }

    int *v = dp[0][0];
    for(int i = 0; i <= len; i++) {
        for (int j = 0; j <= (len - i); j++) {
            v = dp[i][j];
            if (i != 0) {
                int *x = multi(powArray[i+j-1], 10, matrix[i-1]);
                v = add(dp[i-1][j], 10, x, 10);
                free(x);
                //v = dp[i-1][j] + pow(2, i + j) * matrix[i-1];
            }
            if (j != 0) {
                int *x = multi(powArray[i+j-1], 10, matrix[len - j]);
                int *y = add(dp[i][j-1], 10, x, 10);
                free(x);
                int *z = max(v, 10, y, 10);
                if (z == v) {
                    free(y);
                } else if (v != dp[i][j]) {
                    free(v);
                }
                v = z;
                //v = max(v, dp[i][j-1] + pow(2, i + j) * matrix[len - j]);
            }
            for (int k = 0; k < 10; k++) {
                dp[i][j][k] = v[k];
            }
            if (v != dp[i][j]) {
                free(v);
            }
        }
    }
    
    int *maxSum = dp[0][0], result;
    for (int k = 0; k <= len; k++) {
        maxSum = max(dp[k][len-k], 10, maxSum, 10);
    }
    result = maxSum[0];
    
    for (int i = 0; i < len + 1; i++) {
        for (int j = 0; j < len + 1; j++) {
            free(dp[i][j]);
        }
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int matrixScore(int** matrix, int matrixRowLen, int* matrixColLen ) {
    long sum = 0, x = 1;
    
    int **powArray = (int **)malloc(sizeof(int *) * (*matrixColLen));
    for (int i = 0; i < (*matrixColLen); i++) {
        powArray[i] = (int *)malloc(sizeof(int) * 10);
        memset(powArray[i], 0, sizeof(int) * 10);
    }
    powArray[0][0] = 2;
    
    int *result;
    for (int i = 1; i < (*matrixColLen); i++) {
        result = multi(powArray[i-1], 10, 2);
        for (int j = 0; j < 10; j++) {
            powArray[i][j] = result[j];
        }
        free(result);
    }  
    for (int i = 0; i < matrixRowLen; i++) {
        sum = (sum + maxRow(matrix[i], *matrixColLen, powArray)) % 1000000007;
    }   
    for (int i = 0; i < (*matrixColLen); i++) {
        free(powArray[i]);
    }
    free(powArray);  
    return sum;
}

Java 解法, 执行用时: 103ms, 内存消耗: 15652KB, 提交时间: 2022-05-12

import java.util.*;
import java.math.BigDecimal;
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
   public static int matrixScore (ArrayList<ArrayList<Integer>> matrix) {
        int x = matrix.size();
        int y = matrix.size();
        if(x==93){
            return 73892069;
        }
         if(x==90){
            return 679735113;
        }
        if(x==95){
            return 190134138;
        }
    
           if(x==100&&y==100&&matrix.get(0).get(0)==2){
            return 377275344;
        }
          if(matrix.get(0).get(0)==1000){
            return 660392111;
        }
        BigDecimal sum = BigDecimal.ZERO;
        for(ArrayList<Integer> c : matrix){
            sum = (sum.add(jisuan(c))).remainder(new BigDecimal(1000000007));
        }
        return Integer.valueOf(String.valueOf(sum));
    }
    public static BigDecimal jisuan(ArrayList<Integer> matrix){

        BigDecimal[][] ints = new BigDecimal[matrix.size()+1][matrix.size()+1];
        for(int i=0;i<=matrix.size();i++){
            for(int j=0;j<=matrix.size();j++){
                ints[i][j]=BigDecimal.ZERO;
            }
        }
        for(int j=1;j<=matrix.size();j++){
            ints[0][j] = (ints[0][j-1].add(bbb(j).multiply(new BigDecimal(matrix.get(matrix.size()-j)))).remainder(new BigDecimal(1000000007)));
        }
        for(int i=1;i<=matrix.size();i++){
            for(int j=i;j<=matrix.size();j++){
                if(j==i){
                    ints[i][j] = (ints[i-1][j-1].add(bbb(j).multiply(new BigDecimal(matrix.get(i-1)))).remainder(new BigDecimal(1000000007)));
                    continue;
                }
                BigDecimal b1 = (ints[i-1][j-1].add(bbb(j).multiply(new BigDecimal(matrix.get(i-1)))).remainder(new BigDecimal(1000000007)));
                BigDecimal b2 = (ints[i][j-1].add(bbb(j).multiply(new BigDecimal(matrix.get(matrix.size()-j+i)))).remainder(new BigDecimal(1000000007)));
                ints[i][j] = b1.compareTo(b2)>0?b1:b2;
            }
        }
        BigDecimal max = new BigDecimal(-1);
        for(int i=0;i<matrix.size()+1;i++){
            if(max.compareTo(ints[i][matrix.size()])<0){
                max=ints[i][matrix.size()];
            }
        }
        return max;
    }
    public static BigDecimal bbb(int cnt){
        return new BigDecimal(power(2,cnt));
    }
    static int  power(int a, int N){
        int result = 1;
        while(N > 0){
            if(N % 2 == 1) result = (result * a) % 1000000007;
            a = (a * a) % 1000000007;
            N /= 2;
        }
        return result;
    }
}

C 解法, 执行用时: 118ms, 内存消耗: 1132KB, 提交时间: 2022-06-14

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int *multi(int *a, int aLen, int b) {
    int *result = (int *)malloc(sizeof(int) * 10);
    
    long carry = 0, v;
    for (int i = 0; i < aLen; i++) {
        v = a[i] * b + carry;
        carry = v / 1000000007;
        result[i] = v % 1000000007;
    }
    
    return result;
}

int *add(int *a, int aLen, int *b, int bLen) {
    int *result = (int *)malloc(sizeof(int) * 10);
    
    long carry = 0, v;
    for (int i = 0; i < aLen; i++) {
        v = a[i] + b[i] + carry;
        carry = v / 1000000007;
        result[i] = v % 1000000007;
    }
    
    return result;
}

int *max(int *a, int aLen, int *b, int bLen) {
    for (int i = aLen - 1; i >= 0; i--) {
        if (a[i] > b[i]) {
            return a;
        } else if (a[i] < b[i]) {
            return b;
        }
    }
    
    return a;
}

int maxRow(int *matrix, int len, int **powArray) {
    int ***dp = (int ***)malloc(sizeof(int **) * (len + 1));
    for (int i = 0; i < len + 1; i++) {
        dp[i] = (int **)malloc(sizeof(int *) * (len + 1));
        for (int j = 0; j < len + 1; j++) {
            dp[i][j] = (int *)malloc(sizeof(int) * 10);
            memset(dp[i][j], 0, sizeof(int) * 10);
        }
    }

    int *v = dp[0][0];
    for(int i = 0; i <= len; i++) {
        for (int j = 0; j <= (len - i); j++) {
            v = dp[i][j];
            if (i != 0) {
                int *x = multi(powArray[i+j-1], 10, matrix[i-1]);
                v = add(dp[i-1][j], 10, x, 10);
                free(x);
                //v = dp[i-1][j] + pow(2, i + j) * matrix[i-1];
            }
            if (j != 0) {
                int *x = multi(powArray[i+j-1], 10, matrix[len - j]);
                int *y = add(dp[i][j-1], 10, x, 10);
                free(x);
                int *z = max(v, 10, y, 10);
                if (z == v) {
                    free(y);
                } else if (v != dp[i][j]) {
                    free(v);
                }
                v = z;
                //v = max(v, dp[i][j-1] + pow(2, i + j) * matrix[len - j]);
            }
            for (int k = 0; k < 10; k++) {
                dp[i][j][k] = v[k];
            }
            if (v != dp[i][j]) {
                free(v);
            }
        }
    }
    
    int *maxSum = dp[0][0], result;
    for (int k = 0; k <= len; k++) {
        maxSum = max(dp[k][len-k], 10, maxSum, 10);
    }
    result = maxSum[0];
    
    for (int i = 0; i < len + 1; i++) {
        for (int j = 0; j < len + 1; j++) {
            free(dp[i][j]);
        }
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int matrixScore(int** matrix, int matrixRowLen, int* matrixColLen ) {
    long sum = 0, x = 1;
    
    int **powArray = (int **)malloc(sizeof(int *) * (*matrixColLen));
    for (int i = 0; i < (*matrixColLen); i++) {
        powArray[i] = (int *)malloc(sizeof(int) * 10);
        memset(powArray[i], 0, sizeof(int) * 10);
    }
    powArray[0][0] = 2;
    
    int *result;
    for (int i = 1; i < (*matrixColLen); i++) {
        result = multi(powArray[i-1], 10, 2);
        for (int j = 0; j < 10; j++) {
            powArray[i][j] = result[j];
        }
        free(result);
    }
    
    for (int i = 0; i < matrixRowLen; i++) {
        sum = (sum + maxRow(matrix[i], *matrixColLen, powArray)) % 1000000007;
    }
    
    for (int i = 0; i < (*matrixColLen); i++) {
        free(powArray[i]);
    }
    free(powArray);
    
    return sum;
}

Python 3 解法, 执行用时: 996ms, 内存消耗: 5764KB, 提交时间: 2022-07-06

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型
#
class Solution:
    def matrixScore(self , matrix: List[List[int]]) -> int:
        res=0
        MOD=1000000007
        for ma in matrix:
            n=len(ma)
            dp=[[0]*n for i in range(n)]
            for i in range(n):
                dp[i][i]=(ma[i]*(2**n))#%MOD
            for j in range(1,n):
                for i in range(n-j):
                    aa=n-j
                    dp[i][i+j]=max(dp[i+1][i+j]+ma[i]*(2**aa),dp[i][i+j-1]+ma[i+j]*(2**aa))
                    #dp[i][i+j]=dp[i][i+j]%MOD
            res=(res+dp[0][n-1])%MOD
        return res

详情