首页 > 试题广场 >

小萌的副本生涯 【题目描述】 在主城站街

[问答题]

小萌的副本生涯


【题目描述】

在主城站街很久之后,小萌决定不能就这样的浪费时间虚度青春,他打算去打副本。

这次的副本只有一个BOSS,而且BOSS是不需要击杀的,只需要和它比智力…….

BOSS会列出一正整数的序列,由小萌先开始,然后两个人轮流从序列的任意一端取数,取得的数累加到积分里,当所有数都取完,游戏结束。

假设小萌和BOSS都很聪明,两个人取数的方法都是最优策略,问最后两人得分各是多少。

输入

第一行:一个正整数N(2 ≤ N ≤ 100),表示序列中正整数的个数。

第二行至末尾:用空格隔开的N个正整数(1 ≤ a[i] ≤ 200)

输出

只有一行,用空格隔开的两个数,小萌的得分和BOSS的得分。

样例输入

6

4 7 2 9 5 2

样例输出

18 11

#include <iostream>
#include <algorithm>
using namespace std;

//res矩阵用于记录已求出的值,便于今后在遇到重复的(又可叫相同的)子问题时使用
int res[105][105];//ACM竞赛中,习惯性声明比 N的上限=100 大的空间,以防意外溢出
int a[105];//直接取比 N的上限 大的数,不用根据n为多少取多少,因为n是变量不是常量
int n;
//left为剩余字符串最左边那个元素的索引,right同理,isTurn用于控制该谁取数(比如剩奇数个时,该玩家取)
int CalSum(int left,int right,bool isTurn)
{    
    if(res[left][right])//如果已存在这个值,那直接使用,这是动态规划的核心思想
        return res[left][right];
    if(left==right)//如果只剩一个数了
    {
        if(!isTurn)//如果该玩家取数,直接取走并存入res,待其它递归使用
            return res[left][right]=a[left];
        else//如果该BOSS取数,那玩家啥也不取(即取0),但要把0存入res待用
            return res[left][right]=0;
    }  
    if(!isTurn)//如果该玩家取数,那就取从长远来看的max,而不是取当前的max咯~
        return res[left][right]=max(CalSum(left+1,right,!isTurn)+a[left],CalSum(left,right-1,!isTurn)+a[right]);
    else//如果该BOSS取数,那玩家不取数,那被BOSS取数后剩下的,肯定是从长远来看的min咯~
        return res[left][right]=min(CalSum(left+1,right,!isTurn),CalSum(left,right-1,!isTurn));
}

int main()
{
    cin>>n;
    int sum=0;
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int res=CalSum(0,n-1,false);//传入第一位的索引0和最后一位的索引n-1
    cout<<res<<" "<<sum-res<<endl;
    return 0;
}
发表于 2018-01-10 20:54:54 回复(1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(String.valueOf(bf.readLine()));
String[] ss = bf.readLine().split(" ");
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < ss.length; i++) {
queue.offer(Integer.parseInt(String.valueOf(ss[i])));
}
int boss = 0;
int xm = 0;
for (int i = 1; i <= ss.length; i++) {
if (i % 2 != 0) {
if (((LinkedList<Integer>) queue).getFirst() >= ((LinkedList<Integer>) queue).getLast()) {
xm += Integer.parseInt(String.valueOf(((LinkedList<Integer>) queue).getFirst()));
((LinkedList<Integer>) queue).removeFirst();
} else {
xm += Integer.parseInt(String.valueOf(((LinkedList<Integer>) queue).getLast()));
((LinkedList<Integer>) queue).removeLast();
}
} else {
if (((LinkedList<Integer>) queue).getFirst() >= ((LinkedList<Integer>) queue).getLast()) {
boss += Integer.parseInt(String.valueOf(((LinkedList<Integer>) queue).getFirst()));
((LinkedList<Integer>) queue).removeFirst();
} else {
boss += Integer.parseInt(String.valueOf(((LinkedList<Integer>) queue).getLast()));
((LinkedList<Integer>) queue).removeLast();
}
}
}
System.out.println(xm + " " + boss);
}
}

编辑于 2019-04-03 13:29:21 回复(0)

这道题给的样例存在一个问题,那就是当左右两边都是2的时候应该取哪边的2,我个人认为样例的输出应该是15 14


发表于 2018-08-31 09:13:58 回复(0)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;
const int maxN = 1e5 + 5;

int a[maxN];
int main(){
    int t;
    cin >> t;
    for(int i=1;i<=t;i++){
        int n,sum=0;
        cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            sum+=a[i];
        }
        int l=1,r=n,ansa=0,ansb=0;
        while(l<=r){
            if(n==1){
                ansa+=a[n];
                break;
            }if(n==2){
                ansa+=max(a[1],a[2]);
                ansb=sum-ansa;
                break;
            }
            if(a[l]+min(a[r],a[l+1])>a[r]+min(a[r-1],a[l])){
                ansa+=a[l];
                l++;
            }else{
                ansa+=a[r];
                r--;
            }
            if(a[l]+min(a[r],a[l+1])>a[r]+min(a[r-1],a[l])){
                l++;
            }else{
                r--;
            }
        }
        if(abs(ansa)<abs(sum-ansa)){
            int k=abs(sum-ansa);
            swap(ansa,k);
        }
        cout << ansa <<" "<<sum-ansa <<endl;
    }
    return 0 ;
}
/*
8
3 5 3 2 3 1 2 10
ansa  ansb
 10    3
 
*/


发表于 2022-07-21 18:17:46 回复(0)
用双指针能不能做呢?
发表于 2018-10-12 00:34:19 回复(0)
laconic
发表于 2018-02-07 13:45:50 回复(0)
a=int(input("请输入数字序列个数:\n"))
b=input("请输入数字序列,以空格隔开:\n")

list_number=b.split()
num=[int(x) for x in list_number]

anum=num[:a]
anum.sort()
anum.reverse()

score_xiaomeng=anum[::2]
score_boss=anum[1::2]
xiaomeng=0
boss=0
for x in score_xiaomeng:
  xiaomeng=xiaomeng+x
for x in score_boss:
  boss=boss+x
print(xiaomeng,boss)
input("Press anykey to exit......")
exit()

编辑于 2017-12-06 21:12:59 回复(0)

/* ***********************************************
Author        :wsw
Created Time  :2017/11/16 14:26:27
TASK          :选取数字.cpp
LANG          :C++
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int N;
int ant[105];
int sum[105][105];
int mun = 0;
int dfs(int l,int r,int who){
//    cout << l << r << who <<  ":" <<  sum[l][r] << "   ";
//    mun ++;
    if(l==r&&!who){
        return ant[l];
    }
    if(l==r&&who){
        return 0;
    }
    //如果先手拿,拿最优的
    if(!who){
        return sum[l][r] = max(dfs(l,r-1,!who)+ant[r],dfs(l+1,r,!who)+ant[l]);
    }
    if(who){
        return sum[l][r] = min(dfs(l,r-1,!who),dfs(l+1,r,!who));
    }
}
int main()
{
    cin >> N;
    int gg  = 0;
    for(int i = 0;i<N;i++){
        cin >> ant[i];
        gg+=ant[i];
    }
    
    memset(sum,0,sizeof(sum));
    int maxNum = dfs(0,N-1,0);
    cout << maxNum << gg-maxNum << endl; 
//    cout << mun << endl;
    return 0;
}


发表于 2017-11-16 16:06:13 回复(0)
小萌取: 2 9 7 boss取: 5 4 2
发表于 2017-10-27 11:05:24 回复(1)
impor
发表于 2017-09-29 17:18:55 回复(0)
#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int i,j;
    int array[1000];
    for(i=0;i<n;i++)
        cin>>array[i];
    
    int sum1=0,sum2=0;
    
    i=0;
    j=n-1;
    int k=1;
    while(i<=j) 
    {
        if(k%2==1){//萌萌的回合 
            if(array[i]>=array[j]){
            sum1+=array[i++];
            }
            else{
                sum1+=array[j--];
            }
            k++;
        }else//Boss的回合 
        {
                if(array[i]>=array[j]){
            sum2+=array[i++];
            }
            else{
                sum2+=array[j--];
            }
            k++;
        }
    }
    
    cout<<sum2<<" "<<sum1<<endl;
    return 0;
 } 
发表于 2017-09-24 13:32:46 回复(2)
//先用左老师的思想,写一个递归的函数,后面可以改写成dp的矩阵
class Solution {
public:
	int firstsum(int *arr, int left,int right)
	{
		int sum = 0;
		if (left==right)
			return arr[left];
		sum = max(arr[left] + secondsum(arr, left + 1, right), arr[right] + secondsum(arr, left, right - 1));
		return sum;
	}
	int secondsum(int *arr, int left, int right)
	{
		if (left == right)
			return 0;
		
		return min(firstsum(arr, left + 1, right), firstsum(arr, left, right - 1));
	}
	void test()
	{
		int n;
		cin >> n;
		int *arr = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
			sum += arr[i];
		}
		int sum1 = firstsum(arr, 0, n - 1);
		int sum2 = secondsum(arr, 0, n - 1);
		cout << sum1 << " " << sum2 << endl;
	}
};

发表于 2017-08-28 01:36:16 回复(2)
<script> function compare(){ if(arguments[0]!==arguments.length-1){ return false;} var a=0,b=0; var arr=new Array; for(var i=1;i<arguments.length;i++){ arr.push(arguments[i]); } while(arr.length){ a+=com(arr); b+=com(arr); } alert("第一个得分:"+a+" 第二个得分:"+b); } function com(ar){ if(ar[0]<ar[ar.length-1]){ return ar.pop(); }else{ return ar.shift(); } } compare(6,4,7,2,9,5,2); </script>
发表于 2017-08-19 15:30:08 回复(0)

吐槽下这编辑器太不好用了

import java.util.Arrays; 
public class Main{ public static void main(String[] args) {
        System.out.println(Arrays.toString(new Main().findMaxScore(new int[]{4, 7, 2, 9, 5, 2})));
    }  
public int[] findMaxScore(int[] nums){  
//要使用动态规划  
int len = nums.length;  
int[][] dp = new int[2][len]; // 一行记录一个人的得分,最后再判断哪个分数是哪个人的  
dp[0] = Arrays.copyOf(nums, len); 
int a = 0; 
int b = 1; 
for(int i = 1; i<len; i++) // i+1表示当前还剩几个数,倒着推到整个数组  
// 交换ab的值;  
      a = a^b;
      b = a^b;
      a = a^b; 
    for (int j = 0; j < len - i; j++) {
                dp[b][j] = nums[j] + dp[a][j+1] > nums[j+i] + dp[a][j] ? dp[b][j+1] : dp[b][j];
                dp[a][j] = Math.max(nums[j] + dp[a][j+1], nums[j+i] + dp[a][j]);
            } 
//System.out.println(Arrays.toString(dp[0]));  
//System.out.println(Arrays.toString(dp[1]));  
// System.out.println("------------------");  } 
//后拿那个人得分为dp[0][0], 先拿那个人得分为dp[1][0];  
return len % 2 == 0 ? new int[]{dp[1][0], dp[0][0]} : new int[]{dp[0][0], dp[1][0]};
    }
}
编辑于 2017-08-19 11:02:18 回复(0)