C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2020-09-28 20:38:39

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int n,max_=-1,a[maxn],b[maxn];
void dfs(int sum,int pos,int ways){
	if(sum<0||ways<0){
		return;
	}
	if(pos==n){
		if(ways>0)max_=max(max_,sum+a[n]);
		else max_=max(max_,sum);
		return;
	}
	dfs(sum+a[pos]-b[pos],pos+1,ways-1);
	dfs(sum-b[pos],pos+1,ways);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)cin>>b[i];
	dfs(0,1,3);
	cout<<max_<<endl;
}

Python3 解法, 执行用时: 43ms, 内存消耗: 4728K, 提交时间: 2022-01-24 17:59:49

m=-1
n=int(input())
a=[]
a.append(0)
a1=input().split()
for i in range(n):
    a.append(int(a1[i]))
b=[]
b.append(0)
b1=input().split()
for i in range(n-1):
    b.append(int(b1[i]))

def dfs(x,y,s):
    global m
    if x==n:
        if y<3:
            s=s+a[x]
        m=max(m,s)
        return
    if s>=b[x]:
        dfs(x+1,y,s-b[x])
    if s+a[x]>=b[x] and y+1<=3:
        dfs(x+1,y+1,s+a[x]-b[x])

dfs(1,0,0)
print(m)

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2023-07-02 16:53:34

#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005],n;
int sum=0,flag=0,mx=-1;
void dfs(int x,int y,int sum)
{
	if(sum<0)
	{
	return;
}
if(x>n)
{
	mx=max(mx,sum);
	return;
}
    if(y)
    dfs(x+1,y-1,sum+a[x]-b[x]);
    dfs(x+1,y,sum-b[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<n;i++)
	cin>>b[i];
	dfs(1,3,0);
	cout<<mx<<endl;
}