双人数字游戏

using System;
class Program
{
    const int nMax = 1000;
    static int n;
    static int[] a = new int[nMax + 4];
    static Node[][] dp = new Node[nMax - 1][];
    static void Main(string[] args)
    {
        n = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        for (int i = 2; i < n + 2; i++)
        {
            a[i] = int.Parse(str[i - 2]);
        }
        a[0] = a[1] = a[n + 2] = a[n + 3] = 0;
        dp[0] = new Node[n - 1];//最下面一层(只剩两个数的所有情况)
        for (int i = 0; i < n - 1; i++)
        {
            dp[0][i] = new Node();
        }
        int aIndex;
        int lqian, lhou, llqian, llhou, rqian, rhou, rrqian, rrhou;
        //计算最下面一层(每两个数计算一次)
        for (int i = 0; i < n - 1; i++)
        {

            aIndex = i + 2;
            lqian = Math.Abs(a[aIndex - 1] - a[aIndex]);
            lhou = Math.Abs(a[aIndex - 1] - a[aIndex + 1]);
            llqian = Math.Abs(a[aIndex - 2] - a[aIndex]);
            llhou = Math.Abs(a[aIndex - 2] - a[aIndex + 1]);
            rqian = Math.Abs(a[aIndex + 2] - a[aIndex]);
            rhou = Math.Abs(a[aIndex + 2] - a[aIndex + 1]);
            rrqian = Math.Abs(a[aIndex + 3] - a[aIndex]);
            rrhou = Math.Abs(a[aIndex + 3] - a[aIndex + 1]);
            //ll
            if (llqian >= llhou)
            {//如果先手选前一个
                dp[0][i].ll[0] = llqian; //先手选前一个
                dp[0][i].ll[1] = lhou; //后手只能选后一个
            }
            else
            {//如果先选后一个
                dp[0][i].ll[0] = llhou; //先手选后一个
                dp[0][i].ll[1] = lqian; //后手只能选前一个
            }
            //rr
            if (rrqian >= rrhou)
            {
                dp[0][i].rr[0] = rrqian;
                dp[0][i].rr[1] = rhou;
            }
            else
            {
                dp[0][i].rr[0] = rrhou;
                dp[0][i].rr[1] = rqian;
            }
            //lr
            if (lqian >= lhou)
            {
                dp[0][i].lr[0] = lqian;
                dp[0][i].lr[1] = rhou;
            }
            else
            {
                dp[0][i].lr[0] = lhou;
                dp[0][i].lr[1] = rqian;
            }
            //rl
            if (rqian >= rhou)
            {
                dp[0][i].rl[0] = rqian;
                dp[0][i].rl[1] = lhou;
            }
            else
            {
                dp[0][i].rl[0] = rhou;
                dp[0][i].rl[1] = lqian;
            }
        }
        int t1, t2;
        int qian, hou, l, r, ll, rr;
        //主循环
        for (int j = 1; j < n - 1; j++)
        {//计算第j层(只剩j+2个数的所有情况)
            dp[j] = new Node[n - 1 - j];
            for (int i = 0; i < n - 1 - j; i++)
            {
                dp[j][i] = new Node();
            }
            for (int i = 0; i < n - 1 - j; i++)
            {
                qian = i + 2;
                hou = qian + 1 + j;
                l = i + 1;
                ll = i;
                r = hou + 1;
                rr = hou + 2;
                //ll
                t1 = Math.Abs(a[ll] - a[qian]) + dp[j - 1][i + 1].ll[1]; //先手取前
                t2 = Math.Abs(a[ll] - a[hou]) + dp[j - 1][i].lr[1]; //先手取后
                if (t1 >= t2)
                {
                    dp[j][i].ll[0] = t1;
                    dp[j][i].ll[1] = dp[j - 1][i + 1].ll[0];
                }
                else
                {
                    dp[j][i].ll[0] = t2;
                    dp[j][i].ll[1] = dp[j - 1][i].lr[0];
                }
                //rr
                t1 = Math.Abs(a[rr] - a[qian]) + dp[j - 1][i + 1].rl[1];
                t2 = Math.Abs(a[rr] - a[hou]) + dp[j - 1][i].rr[1];
                if (t1 >= t2)
                {
                    dp[j][i].rr[0] = t1;
                    dp[j][i].rr[1] = dp[j - 1][i + 1].rl[0];
                }
                else
                {
                    dp[j][i].rr[0] = t2;
                    dp[j][i].rr[1] = dp[j - 1][i].rr[0];
                }
                //lr
                t1 = Math.Abs(a[l] - a[qian]) + dp[j - 1][i + 1].rl[1];
                t2 = Math.Abs(a[l] - a[hou]) + dp[j - 1][i].rr[1];
                if (t1 >= t2)
                {
                    dp[j][i].lr[0] = t1;
                    dp[j][i].lr[1] = dp[j - 1][i + 1].rl[0];
                }
                else
                {
                    dp[j][i].lr[0] = t2;
                    dp[j][i].lr[1] = dp[j - 1][i].rr[0];
                }
                //rl
                t1 = Math.Abs(a[r] - a[qian]) + dp[j - 1][i + 1].ll[1];
                t2 = Math.Abs(a[r] - a[hou]) + dp[j - 1][i].lr[1];
                if (t1 >= t2)
                {
                    dp[j][i].rl[0] = t1;
                    dp[j][i].rl[1] = dp[j - 1][i + 1].ll[0];
                }
                else
                {
                    dp[j][i].rl[0] = t2;
                    dp[j][i].rl[1] = dp[j - 1][i].lr[0];
                }
            }
        }
        Console.WriteLine(dp[n - 2][0].ll[0] + " " + dp[n - 2][0].ll[1]);
    }
}
class Node
{
    public int[] ll = new int[2];//上次取了左边两个
    public int[] rr = new int[2];//上次取了右边两个
    public int[] lr = new int[2];//上次先手取了左边,后手取了右边
    public int[] rl = new int[2];//上次先手取了右边,后手取了左边
}

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e3+10;
int a[maxn];
int dp[3][3][maxn][maxn][2];
int calc(int x, int y, int apre=2,int bpre = 2){
    int value = 0;
    if(apre == 2){
        return 0;
    }
 
    if(apre==0 && bpre ==0){
        value = a[x-2];
    }else if(apre==0 && bpre ==1){
        value = a[x-1];
    }else if(apre==1 && bpre ==0){
        value = a[y+1];
    }else if(apre==1 && bpre ==1){
        value = a[y+2];
    }
    return value;
}
int dfs(int apre, int bpre, int x, int y, int stat, int &pre_nextans){
    if(x>y){
        return 0;
    }
    if(dp[apre][bpre][x][y][0]!=-1){
        pre_nextans = dp[apre][bpre][x][y][0];
        return dp[apre][bpre][x][y][1];
    }
    int nextans = 0;
    int best_nextans = 0;
    int ans = -1;
    if(stat == 0){
        int value = calc(x,y,apre,bpre);
        // 取左
        int res = dfs(0,bpre,x+1,y,!stat,nextans) + abs(value-a[x]);
        if(res>ans){
            ans = res;
            best_nextans = nextans;
        }
         
        // 取右
        res = dfs(1,bpre,x,y-1,!stat,nextans) + abs(value-a[y]);
        if(res>ans){
            ans = res;
            best_nextans = nextans;
        }
         
         
    }else{
        int value = calc(x,y,bpre,apre);
        // 取左
        int res = dfs(apre,0,x+1,y,!stat,nextans) + abs(value-a[x]);
        if(res>ans){
            ans = res;
            best_nextans = nextans;
        }
         
        // 取右
        res = dfs(apre,1,x,y-1,!stat,nextans) + abs(value-a[y]);
        if(res>ans){
            ans = res;
            best_nextans = nextans;
        }
         
    }
 
    // 便于计算 返回的是下一个的最大值
    dp[apre][bpre][x][y][0] = ans;
    dp[apre][bpre][x][y][1] = best_nextans;
    pre_nextans = ans;
    return best_nextans;
 
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int nextvalue = 0;
        dfs(2,2,0,n-1,0,nextvalue);
        cout<<dp[2][2][0][n-1][0]<<" "<<dp[2][2][0][n-1][1]<<endl;
    }
}

import sys

lines = []

try:
    while True:  # 获取所有输入
        line = sys.stdin.readline().strip()
        if line == "":
            break
        lines.append(line.split())
except:
    pass
N = int(lines[0][0])
l = []
for i in lines[1]:
    l.append(int(i))
del lines


# 搜索路径本质是一个二叉树，那么从树枝向上传播，即可得到最优解
def search(Sa, Sb, l, A, B, term):
    # Sa,Sb为A，B当前的总分
    # l是剩余的数字
    # A,B是A，B上次取的数字
    if len(l) > 0:  # 如果l还没取完
        if term:  # 轮到A
            SaR, SbR = search(Sa + abs(l[0] - A), Sb, l[1:], l[0], B, False)
            SaL, SbL = search(Sa + abs(l[-1] - A), Sb, l[:-1], l[-1], B, False)
            if SaR < SaL:  # A的回合，A会选择对自己有利的
                return SaL, SbL
            else:
                return SaR, SbR
        else:  # 轮到B
            SaR, SbR = search(Sa, Sb + abs(l[0] - B), l[1:], A, l[0], True)
            SaL, SbL = search(Sa, Sb + abs(l[-1] - B), l[:-1], A, l[-1], True)
            if SbR < SbL:  # B的回合，B会选择对自己有利的
                return SaL, SbL
            else:
                return SaR, SbR
    # l被取完后，统计总分
    return Sa, Sb


SaM, SbM = search(0, 0, l, 0, 0, True)
print(SaM, SbM)

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
    int n;
     cin>>n;
    vector<int> nums(n,0);
    for(int i=0;i<n;i++)//输入值
    {
        cin>>nums[i];
    }
    
    vector<int> sa;
    vector<int> sb;
    int left=0;
    int right=n-1;
    sa.emplace_back(0);
    sb.emplace_back(0);
    for(int i=0;i<n;i++)
    {
        if(i%2==0)//sa
        {
            if(abs(nums[left]-sa[sa.size()-1])>=abs(nums[right]-sa[sa.size()-1]))
            {
                 sa.emplace_back(nums[left++]);
            }else
            {
                 sa.emplace_back(nums[right--]);
            }
        }
        else{//sb
             if(abs(nums[left]-sb[sb.size()-1])>=abs(nums[right]-sb[sb.size()-1]))
            {
                 sb.emplace_back(nums[left++]);
            }else
            {
                 sb.emplace_back(nums[right--]);
            }
        }
    }
    
    int saCount=0;//计算sa的值
    for(int i=1;i<sa.size();i++)
    {
        saCount+=abs(sa[i]-sa[i-1]);
    }
     int sbCount=0;//计算sb的值
    for(int i=1;i<sb.size();i++)
    {
        sbCount+=abs(sb[i]-sb[i-1]);
    }
    cout<<saCount<<" "<<sbCount<<endl;
     
 
     
    return 0;
}

#include<iostream>
#include<math.h>
using namespace std;
 
int main()
{
    int n,a[1000],sub1 = 0,sub2 = 0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int l=0,r=n-1,temp1=0,temp2=0;
    while(l<=r)
    {
        if(a[l]==a[r])
        {
            sub1 += abs(a[l] - temp1);
            temp1 = a[l];
            l++;
        }
        else if(abs(a[l] - temp1) > abs(a[r] - temp1))
        {
            sub1 += abs(a[l] - temp1);
            temp1 = a[l];
            l++;
        }
        else{
            sub1 += abs(a[r] - temp1);
            temp1 = a[r];
            r--;
        }
        if(l>r) break;
        if(a[l]==a[r])
        {
            sub2 += abs(a[l] - temp2);
            temp2 = a[l];
            l++;
        }
        else if(abs(a[l] - temp2) > abs(a[r] - temp2))
        {
            sub2 += abs(a[l] - temp2);
            temp2 = a[l];
            l++;
        }
        else{
            sub2 += abs(a[r] - temp2);
            temp2 = a[r];
            r--;
        }
    }
    cout<<sub1<<" "<<sub2;
}

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int N;
int Arr[1000];
vector<int> sa, sb;
int Max_Sa, Max_Sb;
//求绝对值和
int Sum(vector<int> vct)
{
	int sum = 0;
	int temp = 0;
	for (int i = 0; i < vct.size(); i++)
	{
		sum += abs(temp - vct[i]);
		temp = vct[i];
	}
	return sum;
}

void Update_Sa(vector<int> vct)
{
	sa.clear();
	for (int i = 0; i < vct.size(); i++)
		sa.push_back(vct[i]);
}

void Update_Sb(vector<int> vct)
{
	sb.clear();
	for (int i = 0; i < vct.size(); i++)
		sb.push_back(vct[i]);
}

//计算Sa的选择
void Sa_Choise(int begin, int end, vector<int> vct)
{
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	vct.push_back(Arr[begin]);//Sa选择第一个
	begin++;
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	Sa_Choise(++begin, end, vct);//如果Sb选择了第一个
	Sa_Choise(--begin, --end, vct);//如果Sb选择了最后一个
	begin--;//还原
	vct.pop_back();
	vct.push_back(Arr[++end]);//Sa选择最后一个
	end--;
	if (begin > end)
	{
		int suma = Sum(vct);
		if (suma > Max_Sa)
		{
			Max_Sa = suma;
			Update_Sa(vct);
		}
		return;
	}
	Sa_Choise(++begin, end, vct);//如果Sb选择了第一个
	Sa_Choise(--begin, --end, vct);//如果Sb选择了最后一个
}

//计算Sb的选择
void Sb_Choise(int begin, int end, vector<int> vct)
{
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb > Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	vct.push_back(Arr[begin]);//Sb选择第一个
	begin++;
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb > Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	Sb_Choise(++begin, end, vct);//如果Sa选择了第一个
	Sb_Choise(--begin, --end, vct);//如果Sa选择了最后一个
	begin--;//还原
	vct.pop_back();
	vct.push_back(Arr[++end]);//Sb选择最后一个
	end--;
	if (begin > end)
	{
		int sumb = Sum(vct);
		if (sumb >= Max_Sb)
		{
			Max_Sb = sumb;
			Update_Sb(vct);
		}
		return;
	}
	Sb_Choise(++begin, end, vct);//如果Sa选择了第一个
	Sb_Choise(--begin, --end, vct);//如果Sa选择了最后一个
}

void NumberGame()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> Arr[i];
	int begin = 0, end = N - 1;
	int i = 0;
	while (begin <= end)
	{
		Max_Sa = 0, Max_Sb = 0;
		Sa_Choise(begin, end, sa);
		while (sa.size() > i + 1)
			sa.pop_back();
		if (sa[i] == Arr[begin]) begin++;
		else if (sa[i] == Arr[end]) end--;
		if (begin > end)
			break;
		Sb_Choise(begin, end, sb);
		while (sb.size() > i + 1)
			sb.pop_back();
		if (sb[i] == Arr[begin]) begin++;
		else if (sb[i] == Arr[end]) end--;
		i++;
	}
}

int main()
{
	NumberGame();
	cout << Max_Sa << " " << Max_Sb;
	return 0;
}