社区讨论

TLE了七个点

P1541[NOIP 2010 提高组] 乌龟棋参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7y7ao2
此快照首次捕获于
2025/11/21 05:33
4 个月前
此快照最后确认于
2025/11/21 05:33
4 个月前
查看原帖
CPP
#include<cstdio>
#include<ctime>
int N,M;
int a[355],b[155],tong[5];
int maxn;
inline int max(int x,int y){return x>y?x:y;}
inline void dfs(int n,int one,int two,int three,int four,int value){
	value+=a[n];
	if((one==0&&two==0&&three==0&&four==0)||n>=N){
		maxn=max(maxn,value);
		return ;
	}
	if(one)dfs(n+1,one-1,two,three,four,value);
	if(two)dfs(n+2,one,two-1,three,four,value);
	if(three)dfs(n+3,one,two,three-1,four,value);
	if(four)dfs(n+4,one,two,three,four-1,value);
	return ;
}
int main(){
	scanf("%d%d",&N,&M);
	for(register int i=1;i<=N;i++)scanf("%d",&a[i]);
	for(register int i=1;i<=M;i++){
		scanf("%d",&b[i]);
		tong[b[i]]++;
	}
//	double t1=clock();
	dfs(1,tong[1],tong[2],tong[3],tong[4],0);
//	double t2=clock();
	printf("%d\n",maxn/*,t2-t1*/);
	return 0;
}
时间复杂度应是O(404){O(40^4)},也就是O(2560000){O(2560000)},没毛病啊

回复

5 条回复,欢迎继续交流。

正在加载回复...