2 qq 23865443 qq_23865443 于 2016.04.15 12:07 提问

Acm一道动态规划的入门题,还请大神指点 20C

描述
看,Alice和Bob又在玩游戏了。
游戏规则如下:
Alice在纸上写出N个整数a,Bob写出一个整数S。他们轮流从这N个数中取任意个,使得这些数的和等于S。Alice先取。轮到某个人不能取时,这个人就输了。问最后的获胜者是谁。注意:两个人不能有相同取法。
输入
首先输入一个整数T,表示有T组测试数据(T≤100)。
每组测试数据包含两行。第一行包含2个整数N(1≤N≤2000)和S(0≤S≤5000);第二行包含N个整数a(0<a≤100)。
输出
按照样例输出最后的获胜者。
样例输入
2
7 10
1 2 3 4 5 5 10
5 3
1 1 1 1 1
样例输出
Case 1:Alice
Case 2:Bob

3个回答

tusong86
tusong86   2016.04.15 13:15

他们轮流从这N个数中取任意个,使得这些数的和等于S

Alice取了数之后,Bob还能取吗,比如说1 2 3 4 5 5 10
Alice取了1,2,3,4,Bob还能取1,2,3,4吗

qq_23865443
qq_23865443 不能有相同的取法,就是取出的数字不能完全一样
一年多之前 回复
HFUTJungle
HFUTJungle   2016.04.15 19:58

如果在输入的数是保持这种大小顺序的话,下面程序可以得到总共的可能性,当总共的可能性为奇数的时候,Alice赢,当为偶数时,Bob赢。(这应该算简单的实现方法了)
public static int getNumberBySumAndResultArray(int sum,Integer[] resultArray){
int result = 0;
LinkedList stack = new LinkedList();
StringBuffer sb = new StringBuffer();
for(int array : resultArray){
sb.append(array);
}
String[] stackString = new String[]{"",sb.toString()};
stack.push(stackString);
for(int length=stackString[1].length();length>=0;length--){
String[] stackPop = stack.pop();
int num = Integer.valueOf(stackPop[1].charAt(length));
if(sum > num){
stack.push(new String[]{"",stackPop[1].substring(0, length-1)});
}else if(sum == num){
result++;
stack.push(new String[]{"",stackPop[1].substring(0, length-1)});
}else{
stack.push(new String[]{String.valueOf(num),stackPop[1].substring(0, length-1)});
getResults(result,sum,stack);
}
}
return result;
}

 public static void getResults(int result,int sum,LinkedList<String[]> stack){
   int sumChoosed = 0;
   String[] stackArray = stack.pop();
   for(char choosedNumber : stackArray[0].toCharArray()){
     sumChoosed += Integer.valueOf(choosedNumber);
   }
   for(int i = 1;i<stackArray[1].length();i++){
     char leftNumber = stackArray[1].charAt(i);
     int choosedResult = Integer.valueOf(leftNumber) + sumChoosed;
     if(sum < choosedResult){
       stack.push(new String[]{stackArray[0]+leftNumber,stackArray[1].substring(i, stackArray[1].length())});
       getResults(result,sum,stack);
     }else if(sum == choosedResult){
       result++;
       break;
     }else{
       break;
     }
   }
 }
CSDNXIAOD
CSDNXIAOD   2016.04.18 16:56

一道动态规划的题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!