QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288074#7963. 多折较差验证angry_faceTL 0ms0kbC++141.1kb2023-12-21 18:44:582023-12-21 18:44:59

Judging History

你现在查看的是最新测评结果

  • [2023-12-21 18:44:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-12-21 18:44:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int NR=5e3+100;
char s[NR];
struct node
{
	int num1,num2;
	bool operator <(const node &x)const
	{
		if(x.num1==num1) return x.num2>num2;
		else return x.num1>num1;
	}
};
node f[NR][NR];
int num[NR],a[NR];

node dfs(int l,int r)
{
	if(l>r) return (node){0,0};
	if(f[l][r].num1!=0) return f[l][r];
	node ans=(node){1000000000,1000000000};
	for(int i=l;i<=r;i++)
	{
		node now;
		if(i-l<r-i) 
		{
			if(i-l<=num[i]) 
			{
				now=dfs(i+1,r);
				now.num1++;
				now.num2+=(r-i)-(i-l);
			}
		}
		else 
		{
			if(r-i<=num[i]) 
			{
				now=dfs(l,i-1);
				now.num1++;
				now.num2+=(i-l)-(r-i);
			}
		}
		if(now<ans) ans=now;
	}
	return f[l][r]=ans;
}

int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=(s[i]=='^');
	for(int i=1;i<=n;i++)
	{
		int l=i,r=i,sum=0;
		while(true)
		{
			l-=1,r+=1;
			if(l<=0) break;
			if(r>n) break;
			if(a[l]==a[r]) break;
			sum++;
			num[i]=sum;
		}
	}
	node x=dfs(1,n);
	printf("%d %d\n",x.num1,x.num2);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

5000
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

output:


result: