ABC326F改的。

考虑65分怎么做：

我们直接$dp_{i,x,y,0/1}$表示我当前考虑到了第$i$次决策，当前在$x,y$坐标，当前方向是哪一个的最小总代价即可。

空间和时间都稍微有点卡，需要精细实现。

100分的话很简单：

首先，我们能够发现，实际上奇数和偶数下标对应的$A_i$分别管理着$X,Y$方向上能够走到哪，只是正负的问题而已。

为了让最后离原点尽量近，我们需要让这两个维度的绝对值都尽量小。

所以，我们对奇数下标，偶数下标分别$dfs$一遍，求出答案对应的$X,Y$的绝对值，也就是说，答案只有这四种选择了。

这一步的时间复杂度是$O(2^{n/2})$。

接下来，考虑到$n=40$刚好是$20$的两倍，我们考虑先搜索前$n/2$个点的决策，再搜索后$n/2$个点的决策，这样各有$2^{n/2}$种方案，显然，只有当前半段对应的$x_1,y_1$和后半段对应的$x_2,y_2$加一起恰好满足$|x_1+x_2|=X,|y_1+y_2|=Y$，这样才能满足题目上离原点最近的要求。

也就是说，我们在搜索完两边之后，只枚举左半边的$x_1,y_1$，就知道右边的$x_2,y_2$是谁了，用个map存一下就可以了。

时间复杂度$O(2^{n/2}log{2^{n/2}})$

其实加强到$n=80$也可以做，两个维度分开考虑就是两个上述问题。

#include<bits/stdc++.h>
#define maxn 50
#define ll long long
#define mod 998244353
using namespace std;
int n;
int A[maxn],L[maxn],R[maxn];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1}; //顺指针加一，逆时针减一 
map<pair<int,int>,int> vis[4];
int ansx=999999999,ansy=999999999;
void dfs(int i,int now,int &ans)
{
	if (i>n) {ans=min(ans,abs(now)); return;}
	dfs(i+2,now+A[i],ans); dfs(i+2,now-A[i],ans);
	return;
}

void dfs2(int i,int f,int x,int y,int cost,int of)
{
	if (i==n+1) 
	{
		if (!vis[of].count(make_pair(x,y)) || vis[of][make_pair(x,y)]>cost) vis[of][make_pair(x,y)]=cost;
		return;
	}
	int nf=(f+1)%4;
	dfs2(i+1,nf,x+dx[nf]*A[i],y+dy[nf]*A[i],cost+L[i],of);
	nf=(f-1+4)%4;
	dfs2(i+1,nf,x+dx[nf]*A[i],y+dy[nf]*A[i],cost+R[i],of);
	return;
}

int ans=999999999;
void dfs3(int i,int f,int x,int y,int cost)
{
	if (i==n/2+1)
	{
		for (int X=-ansx;X<=ansx;X+=ansx+ansx)
		for (int Y=-ansy;Y<=ansy;Y+=ansy+ansy)
		{
			if (vis[f].count(make_pair(X-x,Y-y)))
				ans=min(ans,cost+vis[f][make_pair(X-x,Y-y)]);
			if (X==ansx && Y==ansy) return;
			if (Y==ansy) break;
		}
		return;
	}
	int nf=(f+1)%4;
	dfs3(i+1,nf,x+dx[nf]*A[i],y+dy[nf]*A[i],cost+L[i]);
	nf=(f-1+4)%4;
	dfs3(i+1,nf,x+dx[nf]*A[i],y+dy[nf]*A[i],cost+R[i]);
	return;
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>A[i];
	for (int i=1;i<=n;i++) cin>>L[i];
	for (int i=1;i<=n;i++) cin>>R[i];
	dfs(1,0,ansy); dfs(2,0,ansx);
	if ((n/2+1)&1) dfs2(n/2+1,0,0,0,0,0),dfs2(n/2+1,2,0,0,0,2);
	else dfs2(n/2+1,1,0,0,0,1),dfs2(n/2+1,3,0,0,0,3);
	dfs3(1,0,0,0,0);
	cout<<ans<<endl;
}

补一个 20 分的暴力做法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40;
int n;
int a[MAXN + 5], L[MAXN + 5], R[MAXN + 5];
int minDis, minCost;
// 处于 (x,y) 的位置，之前的总代价为 pre，方向为 fx
// x 正方向为 0，顺时针依次 0,1,2,3
// 要进行第 now 次抉择
void dfs(int now, int x, int y, int pre, int fx)
{
    if (now > n)
    {
        if (x * x + y * y < minDis)
        {
            minDis = x * x + y * y;
            minCost = pre;
        }
        else if (x * x + y * y == minDis)
            minCost = min(minCost, pre);
        return;
    }
    if (fx == 0)
    {
        dfs(now + 1, x, y - a[now], pre + L[now], 1);
        dfs(now + 1, x, y + a[now], pre + R[now], 3);
    }
    else if (fx == 1)
    {
        dfs(now + 1, x - a[now], y, pre + L[now], 2);
        dfs(now + 1, x + a[now], y, pre + R[now], 0);
    }
    else if (fx == 2)
    {
        dfs(now + 1, x, y + a[now], pre + L[now], 3);
        dfs(now + 1, x, y - a[now], pre + R[now], 1);
    }
    else if (fx == 3)
    {
        dfs(now + 1, x + a[now], y, pre + L[now], 0);
        dfs(now + 1, x - a[now], y, pre + R[now], 2);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    minDis = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        minDis += a[i];
    }
    minDis *= minDis;
    for (int i = 1; i <= n; i++)
        cin >> L[i];
    for (int i = 1; i <= n; i++)
        cin >> R[i];
    dfs(1, 0, 0, 0, 0);
    cout << minCost << "\n";
    return 0;
}