这题不能用记忆化搜索吗,全部都tle了
查看原帖
这题不能用记忆化搜索吗,全部都tle了
504237
lk323232楼主2022/8/17 17:30

我以为也许可以过一两个点的

#include<bits/stdc++.h>
using namespace std;
int n,a[2000001],dp[2000001],vis[2000001],mx=0x7fffffff;
void dfs(int loc,int sum,int flag){
	if(loc>n){
		mx=min(mx,sum);
		return ;
	}
	if(!vis[loc+1]&&sum+a[loc+1]<dp[loc+1]) {
		vis[loc+1]=1;
		dp[loc+1]=sum+a[loc+1];
		if(flag<2) dfs(loc+1,sum+a[loc+1],flag+1);
		else dfs(loc+1,sum+a[loc+1],flag);
		vis[loc+1]=0;
	}
	if(!vis[loc+2]&&sum+a[loc+2]<dp[loc+2]&&flag>0){
		vis[loc+2]=1;
		dp[loc+2]=sum+a[loc+2];
		dfs(loc+2,dp[loc+2],flag);
		vis[loc+2]=0;
	}
	if(!vis[loc+3]&&sum+a[loc+3]<dp[loc+3]&&flag>0){
		vis[loc+3]=1;
		dp[loc+3]=sum+a[loc+3];
		dfs(loc+3,dp[loc+3],flag);
		vis[loc+3]=0;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),dp[i]=0x7fffffff;
	dp[n+1]=0x7fffffff;dp[n+2]=0x7ffffff;dp[n+3]=0x7fffffff;
	dfs(0,0,2);
	cout<<mx;
	return 0;
}
2022/8/17 17:30
加载中...