Question

java算法题,要用java语言写的。

矩阵取数游戏

【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
4. 游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

【要求】
【数据输入】输入有多个测试数据，每个包括n+1行：
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
1<=n, m<=80, 0<=aij<=1000

【数据输出】对每个数据，输出一行，为一个整数，即输入矩阵取数后的最大得分。相邻两个输出间用一个空行隔开。

【样例输入】
1 4
4 5 0 5
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

【样例输出】
122

316994

Answer 1

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MyStack {
public static void main(String[] args) {
List<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
Scanner scanner = new Scanner(System.in);
// 获取第一行输入的数据
String s1 = scanner.nextLine();
String[] ss1 = s1.split(" ");
List<Integer> listRow;
String sTemp;
String[] ssTemp;
for (int i = 0; i < Integer.parseInt(ss1[0]); i++) {
listRow = new ArrayList<Integer>();
sTemp = scanner.nextLine();
ssTemp = sTemp.split(" ");
for (int j = 0; j < ssTemp.length; j++) {
listRow.add(Integer.parseInt(ssTemp[j]));
}
listAll.add((ArrayList<Integer>) listRow);

}
List<ArrayList<Integer>> xulie = new ArrayList<ArrayList<Integer>>();
xulie = xl(Integer.parseInt(ss1[1]));
int sum = 0;
for (int i = 0; i < listAll.size(); i++) {
sum += selectMaxRow(xulie, listAll.get(i));
}
System.out.println("总得分:" + sum);
}

/**
* 算出指定数组，按照某种序列计算得分后，最大的结果
*
* @param xulie
* @param listRow
*/
private static int selectMaxRow(List<ArrayList<Integer>> xulie,
List<Integer> listRow) {
int maxRow = 0;
for (int i = 0; i < xulie.size(); i++) {
if (calRow(xulie.get(i), listRow) > maxRow) {
maxRow = calRow(xulie.get(i), listRow);
}
}
return maxRow;
}

/**
* 根据某种序列，计算指定数组的得分
*
* @param listRow
* @return
*/
private static int calRow(List<Integer> xul, List<Integer> listRow) {
int sumRow = 0;
for (int i = 0; i < xul.size(); i++) {
sumRow += listRow.get(xul.get(i) - 1) * abI(i + 1);
}
return sumRow;
}

/**
* 计算2的i次方
*
* @param i
* @return
*/
private static Integer abI(int abi) {
int sumi = 1;
for (int i = 0; i < abi; i++) {
sumi *= 2;
}
return sumi;
}

/**
* 对于一个m列的数组，每次取行首或者行尾，所得出的取值顺序序列一共有2^(m-1)种. exp: m=3,return: {1,2,3}
* {1,3,2} {3,1,2} {3,2,1}。 返回的数组，其中各项的位置不重要
*
* @param m
* @return 返回数组的每一种取值顺序序列
*/
public static List<ArrayList<Integer>> xl(int m) {
List<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>();
l.add(new ArrayList<Integer>());
for (int i = 1; i <= m; i++) {
if (i == 1) {
l.get(0).add(1);
} else {
int lsize = l.size();
for (int j = 0; j < lsize; j++) {
List<Integer> ltemp = new ArrayList<Integer>();
copy(ltemp, l.get(j));
// 添加一项到数组头位置，并赋值为 1
ltemp.add(0, 1);
l.add((ArrayList<Integer>) ltemp);

// 在该序列的最前面 添加 i
l.get(j).add(0, i);
}
}
}
return l;
}

/**
* 把List lf里面的值+1后 复制到ltemp中去
*
* @param ltemp
* @param lf
*/
private static void copy(List<Integer> ltemp, ArrayList<Integer> lf) {
for (int i = 0; i < lf.size(); i++) {
ltemp.add(lf.get(i) + 1);
}
}

}

Answer 2

表示一行 取后所有的情况 s、e为前后指针，i为取第i个，sum为和
void trset(int s,int e,int i,int sum){
if(s>=e)获取和放到一个集合中
else{
int num1=sum+a[s]*2^i;
int num2=sum+a[e]*2^i;
i++;
trset(s++,e,i,num1);
trset(s,e--,i,num2);
}
}
从集合中取到最大的
trset(0,n-1,1,0);

Answer 3

同意楼上，程序有些繁琐。。。

Answer 4

这个悬赏 200分
估计有人帮你写