这样写寄搜怎么优化才能不T呢
查看原帖
这样写寄搜怎么优化才能不T呢
601681
Hanggoash楼主2022/10/31 20:44

rt

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=5e3+100;
int n,m,k,team[maxn];
int f[maxn][maxn],nex[maxn];
inline void input()
{
	memset(f,-1,sizeof f);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)scanf("%d",&team[i]),nex[i]=i+1;
	nex[n]=1;
}

inline int dfs(int i,int j)
{
	if(j==1)return f[i][j]=0;
	if(f[i][j]!=-1)return f[i][j];
	int tar=(team[i]==team[nex[i]]);
	for(int d=max(j-k,1);d<=j-1;++d)
	{
		if(f[nex[i]][d]==-1)f[nex[i]][d]=dfs(nex[i],d);
		if(f[nex[i]][d]==tar)return 1;
	}
	return 0;	
}
template <typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);	
} 

int main()
{
	input();
	for(int i=1;i<=n;++i)
	{
		int tmp=dfs(i,m);
		if(team[i]==1)
			wr(tmp==1?1:0),putchar(' ');
		else 
			wr(tmp==1?0:1),putchar(' ');
	}
	return 0;
}
2022/10/31 20:44
加载中...