QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288074 | #7963. 多折较差验证 | angry_face | TL | 0ms | 0kb | C++14 | 1.1kb | 2023-12-21 18:44:58 | 2023-12-21 18:44:59 |
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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...