求助,dfsTLE了一个点
查看原帖
求助,dfsTLE了一个点
421634
QT___楼主2023/6/3 09:04
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAXN 60
     
using namespace std;

int n,m;
int a[MAXN],sum[MAXN];
int minn=0x3f3f3f3f,maxn;
int huan;
void dfs(int nowm,int num,int cmt){
	if(cmt==m){
//		if(nowm>n) nowm=nowm-1;
		int sumnum=sum[n]-sum[nowm-1]+sum[huan-1];
		if(sumnum<0) sumnum=10-(-sumnum%10);
		else sumnum=sumnum%10;
		num=num*sumnum;
		maxn=max(maxn,num);
		minn=min(minn,num);
		return;
	}
	int l=min(n-1,n-(m-cmt)+1);
	for(int i=nowm;i<=l;i++){
		int sumnum=sum[i]-sum[nowm-1];
		if(sumnum<0) sumnum=10-(-sumnum%10);
		else sumnum=sumnum%10;
		dfs(i+1,num*sumnum,cmt+1);
	}
	return;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n-m+1;i++){
		for(int j=1;j<=i;j++){
			huan=j;
			dfs(j,1,1);
		}
	}
	printf("%d\n%d", minn, maxn);
    return 0;
}
2023/6/3 09:04
加载中...