朴素搜索,但第五个点WA了
查看原帖
朴素搜索,但第五个点WA了
250699
mot1ve楼主2021/11/10 16:16

能看出来哪错的赏一个关注

//断链成环 
//一共m个组,dfs搜一遍
//一个数字有两个决策:与上一个归为一类/新开一类
//不能超过m,不能少于m 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans1=1e18,ans2=-1e18;
int a[60],b[60];
//正在考虑第几个数,有几组了,这一组内的和,总的得分 
void dfs1(int x,int cnt,int sum,int res)
{
	if(x>n) 
	{
		int c=abs(sum/10);
		if(sum%10!=0)
		c++;
		res*=((sum+10*c)%10);//最后一组还没算 
		if(cnt==m)//只有等于m才合法 
		{
			ans1=min(ans1,res);
			ans2=max(ans2,res);
		}
		return ;
	}
	if(cnt==m)//达到上限 
	{	
		dfs1(x+1,cnt,sum+a[x],res);
	}
	else
	{
		dfs1(x+1,cnt,sum+a[x],res);
		int c=abs(sum/10);
		if(sum%10!=0)
		c++;
		dfs1(x+1,cnt+1,a[x],res*((sum+10*c)%10)); 
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
		b[i+n]=b[i];
	}
	int p1=1,p2=n;
	while(p2<=2*n)
	{
		int cnt=1;
		for(int i=p1;i<=p2;i++)
		{
			a[cnt++]=b[i];
		}
		dfs1(2,1,a[1],1);
		p1++;
		p2++;
	}
	cout<<ans1<<endl<<ans2;
	return 0;
}
2021/11/10 16:16
加载中...