Untitled

 avatar
unknown
plain_text
2 years ago
1.1 kB
4
Indexable
#include<iostream>
using namespace std;

int N,K,M;
int ans;
int R[20];

bool check()
{
	for(int i=0;i<=N-K;i++)
	{
		int r_max=0,cnt=1;
		for(int j=i;j<=i+K-1;j++)
		{
			//r_max=R[j];
			if(R[j]>r_max)
			{
				r_max=R[j];
				cnt=1;
			}
			else  if(R[j]==r_max)
			{
				cnt++;
			}
		}
		if(cnt>=M)
			return 0;
	}
	return 1;
}

void backtrack(int k,int sum)
{
	if(sum>ans)
		return;
	if(check())
	{
		ans=min(ans,sum);
		return;
	}
	if(k==N)
	{
		return;
	}
	for(int i=0;i<=1;i++)
	{
		if(i==0)
			backtrack(k+1,sum);
		else
		{
			R[k]++;
			backtrack(k+1,sum+1);
			R[k]--;
		}
	}
}
void reset()
{
	for(int i=0;i<N;i++)
			R[i]=0;
}
int main()
{
	int T;
	cin>>T;
	for(int tc=1;tc<=T;tc++)
	{
		cin>>N>>K>>M;
		reset();
		for(int i=0;i<N;i++)
			cin>>R[i];
		if(M==1)
		{
			cout<<"#"<<tc<<" "<<-1<<endl;
		}
		else
		{
		ans=1000000;
		backtrack(0,0);
		if(ans==1000000)
			cout<<"#"<<tc<<" "<<-1<<endl;
		else 
			cout<<"#"<<tc<<" "<<ans<<endl;
		}
	}
	return 0;
}
Editor is loading...