招商校招第二题

题目

A，B两名参赛者，游戏规则如下：
有m个不同身高的同事站成一排，A ,B 两个参赛者依次从最左边开始选择一名或两名同事出列(A先开始)，直到所有同事都被选择完为止，最终计算两名参赛者所选择的同事的身高总和，总身高更高的人获胜。假设两名参赛者足够聪明，请判断第一名参赛者A是输还是赢

输入：
输入第一行为一个正整数，代表同事的数量m
输入的第二行为m个正整数，代表每位同事的身高
输出：
如果参赛者A赢，则输出true，如果输或者打平则输出false

题意

这道题和之前分金子的题一样，同样可以分为相同的子问题，下面给出一种复杂的方法：
假设身高数组为[h1,h2,h3,h4,h5,….hm]，A此时的身高总和为sumA，B此时的身高总和为sumB，设定flag为true时，为A先选，flag为false时，为B先选；即flag=true
如上初始条件为：[h1,h2,h3,h4,h5,….hm]，sumA=0, sumB=0, flag=true
设递归函数为txsf(),初始条件即为函数参数
此时A先选，可以选一个或者两个，即
txsf([h2,h3,h4,h5,….hm]，sumA+h1, sumB, flag=false)或者
txsf([h3,h4,h5,….hm]，sumA+h1+h2, sumB, flag=false)
我们只需要判断txsf的返回值，哪个大A就选那个大的
上面的递归函数相当于一个子问题，只是参数变了，那么我们在递归函数中设定出口，即可得出递归函数的值，进而判断如何选取

java实现

这里给出上面复杂思路的算法

import java.util.Scanner;

public class XYK02 {
    //递归方式分解问题
	//a为sumA ，b为sumB ；flag为true表示a选，false表示b选；index为w的指针；w为身高数组
	public static String txsf(int a,int b,Boolean flag,int index,int[] w){
		int a1,a2,b1,b2;
		//如果index已经指向最后一个元素的下一个，表示已经选择完毕
		if(index==w.length){
			return String.valueOf(a)+"#"+String.valueOf(b);//将a和b用#连接返回
		}
		//为true表示A选
		if(flag==true){
			//如果index指向最后一个元素，直接让A选即可
			if(index==w.length-1){
				return String.valueOf(a+w[index])+"#"+String.valueOf(b);
			}else{
				//否者判断是选一个还是选择两个
				
				String aString=txsf(a+w[index]+w[index+1], b, false, index+2, w);
				String bString=txsf(a+w[index], b, false, index+1, w);
				a1=Integer.parseInt(aString.split("#")[0]);
				a2=Integer.parseInt(bString.split("#")[0]);
				b1=Integer.parseInt(aString.split("#")[1]);
				b2=Integer.parseInt(bString.split("#")[1]);
				//因为此时是A先选，因此只用考虑A最优的情况，而B只有跟随的份
				if(a1>a2){
					a=a1;
					b=b1;
				}else{
					a=a2;
					b=b2;
				}
			}
		}else{
			//如果index指向最后一个元素，直接让B选即可
			if(index==w.length-1){
				return String.valueOf(a)+"#"+String.valueOf(b+w[index]);
			}else{
				//判断是选一个还是选择两个
				
				String aString=txsf(a, b+w[index]+w[index+1], true, index+2, w);
				String bString=txsf(a, b+w[index], true, index+1, w);
				a1=Integer.parseInt(aString.split("#")[0]);
				a2=Integer.parseInt(bString.split("#")[0]);
				b1=Integer.parseInt(aString.split("#")[1]);
				b2=Integer.parseInt(bString.split("#")[1]);
				
				//因为此时是B先选，因此只用考虑B最优的情况，而A只有跟随的份
				if(b1>b2){
					b=b1;
					a=a1;
				}else{
					b=b2;
					a=a2;
				}
			}
		}
		return String.valueOf(a)+"#"+String.valueOf(b);
	}

	public static void main(String[] args) {
		int m;
		int w[];
		String string;
		//读取输入
		Scanner scanner = new Scanner(System.in);
		m = scanner.nextInt();
		w=new int[m];
		for(int i=0;i<m;i++){
			w[i]=scanner.nextInt();
		}
		scanner.close();
		string=txsf(0,0,true,0,w);
		System.out.println(Integer.parseInt(string.split("#")[0])>Integer.parseInt(string.split("#")[1]));
	}
}

改天补上正序方式分解算法