为什么不能用剩下的步数和和位置来作为记忆化搜索依据
查看原帖
为什么不能用剩下的步数和和位置来作为记忆化搜索依据
752358
xxxsw楼主2022/10/22 15:21
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
std::vector<int>v;
int p[400][400];
int s[5],l[400];
int sum=1;
  //k当前位置,t为剩余步数
int bfs(int k,int t)
{
	if(k==sum)return l[sum];
	if(p[k][t])return p[k][t];
	int su=0;
	for(int i=1;i<=4;i++)
	{
		if(s[i]){
			s[i]--;
			su=max(su,bfs(k+i,t-1)+l[k]);
			s[i]++;
		}
	}
	//cout<<su<<" "<<k<<endl;
	return p[k][t]=su;
}
int main ()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)cin>>l[i];
	for(int i=1;i<=m;i++)
	{
		int a;
		cin>>a;
		s[a]++;
		sum+=a;
	}
	cout<<bfs(1,m);
} 
2022/10/22 15:21
加载中...