QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #779654 | #5190. 小 E 爱消除 | ffffyc | AC ✓ | 267ms | 73336kb | C++14 | 5.3kb | 2024-11-24 20:49:04 | 2024-11-24 20:49:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
int len=0;
char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline int read(){
reg char ch=gh();
reg int x=0;
reg char t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
return t?-x:x;
}
inline void putc(char ch){
out[len++]=ch;
}
template<class T>
inline void write(T x){
if(x<0)putc('-'),x=-x;
if(x>9)write(x/10);
out[len++]=x%10+48;
}
inline void flush(){
fwrite(out,1,len,stdout);
len=0;
}
inline char getc(){
char ch=gh();
while(ch<'A'||ch>'Z') ch=gh();
return ch;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=50+5,INF=1e9+10;
/*
struct node{
int c,s,r;
node(int A=0,int B=0,int C=0){ c=A,s=B,r=C; }
inline friend node operator+(const node &a,const node &b){ return node(a.c+b.c,a.s+b.s,max(a.r,b.r+a.c)); }
};
*/
inline pii operator+(const pii &a,const pii &b){ return mpr(a.fir+b.fir,max(a.sec,b.sec+a.fir)); }
inline pii operator*(const pii &a,const pii &b){ return mpr(a.fir+b.fir,a.sec+b.sec); }
int n,c[N];
pii g[N][N],f[N][N][N][N];
inline void upd(pii &x,pii y){ x=min(x,y); }
inline pii F(int l1,int r1,int l2,int r2){//clear [l_1,r_1] [l_2,r_2]
pii tp;
if(l1>r1&&l2>r2) tp=mpr(0,0);//,printf("A ");
else if(l1>r1) tp=f[1][0][l2][r2];//,printf("B %d %d ",g[l2][r2].fir,g[l2][r2].sec);
else if(l2>r2) tp=f[l1][r1][r1+1][r1];//,printf("C ");
else tp=f[l1][r1][l2][r2];//,printf("D ");
if(tp.fir) tp=mpr(INF,INF);
// printf("[%d,%d] [%d,%d] %d %d\n",l1,r1,l2,r2,tp.fir,tp.sec);
return tp;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
c[i]=read();
for(int s=1;s<=n;s++){
for(int l=1,r=s;r<=n;l++,r++){
g[l][r]=mpr(INF,INF);
upd(g[l][r],g[l+1][r]*mpr(1,1));
upd(g[l][r],g[l][r-1]*mpr(1,1));
// if(l==1&&r==9) printf("?? %d %d\n",g[l][r].fir,g[l][r].sec);
for(int k=l+1;k<=r;k++)
if(c[l]==c[k]){
for(int p=l+1;p<=k;p++){
pii tp=mpr(1,1)+F(l+1,p-1,k+1,r)+mpr(-1,1)+g[p][k-1];
upd(g[l][r],mpr(1,1)+F(l+1,p-1,k+1,r)+mpr(-1,1)+g[p][k-1]);
// if(l==1&&r==9) printf("%d %d %d %d\n",k,p,tp.fir,tp.sec);
}
for(int p=k+1;p<=r;p++){
pii tp=mpr(1,1)+F(l+1,k-1,p+1,r)+mpr(-1,1)+g[k+1][p];
upd(g[l][r],mpr(1,1)+F(l+1,k-1,p+1,r)+mpr(-1,1)+g[k+1][p]);
// if(l==1&&r==9) printf("%d %d %d %d\n",k,p,tp.fir,tp.sec);
}
// if(l==1&&r==9) printf("A %d %d %d\n",k,g[l][r].fir,g[l][r].sec);
}
for(int k=l;k<=r-1;k++)
if(c[r]==c[k]){
for(int p=k;p<=r-1;p++){
pii tp=mpr(1,1)+F(l,k-1,p+1,r-1)+mpr(-1,1)+g[k+1][p];
upd(g[l][r],mpr(1,1)+F(l,k-1,p+1,r-1)+mpr(-1,1)+g[k+1][p]);
// if(l==1&&r==9) printf("%d %d %d %d %d %d\n",k,p,tp.fir,tp.sec,F(l,k-1,p+1,r-1).fir,F(l,k-1,p+1,r-1).sec);
}
for(int p=l;p<=k-1;p++){
pii tp=mpr(1,1)+F(l,p-1,k+1,r-1)+mpr(-1,1)+g[p][k-1];
upd(g[l][r],mpr(1,1)+F(l,p-1,k+1,r-1)+mpr(-1,1)+g[p][k-1]);
// if(l==1&&r==9) printf("%d %d %d %d %d %d\n",k,p,tp.fir,tp.sec,F(l,p-1,k+1,r-1).fir,F(l,p-1,k+1,r-1).sec);
}
// if(l==1&&r==9) printf("B %d %d %d\n",k,g[l][r].fir,g[l][r].sec);
}
// printf("[%d,%d] %d %d\n",l,r,g[l][r].fir,g[l][r].sec);
}
for(int len1=0,len2=s;len2>=0;len1++,len2--)
for(int l1=1,r1=len1;r1<=n;l1++,r1++)
for(int l2=r1+1,r2=l2+len2-1;r2<=n;l2++,r2++){
f[l1][r1][l2][r2]=mpr(INF,INF);
if(s&1) continue;
if(!len1&&l1>1) continue;
if(!len2&&r2>r1) continue;
if(len1){
for(int p=l1+1;p<=r1;p++)
if(c[l1]==c[p])
for(int q=l2;q<=r2+1;q++)
upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1+1,p-1,q,r2)+mpr(-1,1)+F(p+1,r1,l2,q-1));
for(int q=l2;q<=r2;q++)
if(c[l1]==c[q])
for(int p=l1;p<=r1;p++)
upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1+1,p,q+1,r2)+mpr(-1,1)+F(p+1,r1,l2,q-1));
}
if(len2){
for(int p=l1;p<=r1;p++)
if(c[r2]==c[p])
for(int q=l2;q<=r2;q++)
upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1,p-1,q,r2-1)+mpr(-1,1)+F(p+1,r1,l2,q-1));
// if(l1==1&&r1==0&&l2==2&&r2==5) printf("* %d %d\n",f[l1][r1][l2][r2].fir,f[l1][r1][l2][r2].sec);
for(int q=l2;q<=r2-1;q++)
if(c[r2]==c[q])
for(int p=l1-1;p<=r1;p++){
pii tp=mpr(1,1)+F(l1,p,q+1,r2-1)+mpr(-1,1)+F(p+1,r1,l2,q-1);
upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1,p,q+1,r2-1)+mpr(-1,1)+F(p+1,r1,l2,q-1));
// if(l1==1&&r1==0&&l2==2&&r2==5) printf("* %d %d %d %d\n",p,q,F(l1,p,q+1,r2-1).fir,F(l1,p,q+1,r2-1).sec);
}
}
if(f[l1][r1][l2][r2].fir>=INF) continue;
// printf("[%d,%d] [%d,%d] %d %d\n",l1,r1,l2,r2,f[l1][r1][l2][r2].fir,f[l1][r1][l2][r2].sec);
}
}
write(g[1][n].fir),putc(' '),write(g[1][n].sec),putc('\n');
flush();
}
/*
50
50 34 43 39 50 21 50 27 34 7 50 2 7 27 2 43 21 43 7 7 39 34 7 32 50 34 50 34 32 34 32 34 21 27 7 2 50 34 27 39 39 7 21 21 7 27 39 50 34 7
*/
详细
Test #1:
score: 100
Accepted
time: 187ms
memory: 71284kb
input:
50 14 31 14 31 14 31 14 14 14 31 14 14 14 31 31 31 14 31 31 31 31 14 31 14 31 14 31 14 31 31 14 31 14 14 31 31 14 31 31 14 14 31 31 14 31 31 14 14 31 14
output:
0 3
result:
ok single line: '0 3'
Test #2:
score: 0
Accepted
time: 134ms
memory: 71156kb
input:
50 1 18 18 18 50 1 50 1 18 18 50 18 18 18 50 1 50 1 18 50 18 50 50 50 18 18 18 50 50 1 18 18 18 18 50 1 50 1 50 50 18 1 50 50 50 1 1 18 18 50
output:
2 3
result:
ok single line: '2 3'
Test #3:
score: 0
Accepted
time: 57ms
memory: 73276kb
input:
50 6 5 13 5 36 13 29 29 29 5 36 5 6 13 5 5 6 5 29 29 5 5 29 5 13 6 13 13 5 13 5 13 29 39 39 39 6 6 6 39 5 39 13 13 29 13 5 6 6 39
output:
2 8
result:
ok single line: '2 8'
Test #4:
score: 0
Accepted
time: 44ms
memory: 71400kb
input:
50 50 34 43 39 50 21 50 27 34 7 50 2 7 27 2 43 21 43 7 7 39 34 7 32 50 34 50 34 32 34 32 34 21 27 7 2 50 34 27 39 39 7 21 21 7 27 39 50 34 7
output:
10 11
result:
ok single line: '10 11'
Test #5:
score: 0
Accepted
time: 22ms
memory: 71224kb
input:
50 10 49 41 28 26 11 5 24 29 18 39 38 13 16 26 37 40 25 50 44 26 13 49 24 2 6 4 3 38 4 15 37 41 37 34 25 20 24 15 38 26 15 26 10 6 7 47 13 31 6
output:
38 38
result:
ok single line: '38 38'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5608kb
input:
1 1
output:
1 1
result:
ok single line: '1 1'
Test #7:
score: 0
Accepted
time: 267ms
memory: 71492kb
input:
50 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22
output:
0 2
result:
ok single line: '0 2'
Test #8:
score: 0
Accepted
time: 50ms
memory: 71232kb
input:
50 19 40 9 10 19 40 12 9 19 19 7 9 9 7 12 19 19 7 19 40 46 12 10 46 12 7 19 7 19 12 7 10 7 46 12 7 9 9 10 12 7 7 10 46 19 12 7 9 10 40
output:
6 9
result:
ok single line: '6 9'
Test #9:
score: 0
Accepted
time: 58ms
memory: 71200kb
input:
50 26 9 1 1 1 29 1 9 26 20 20 21 1 26 21 21 1 1 29 26 29 21 1 1 21 1 26 21 21 1 26 20 9 1 29 29 29 21 29 20 29 21 20 29 1 1 9 9 29 29
output:
4 5
result:
ok single line: '4 5'
Test #10:
score: 0
Accepted
time: 44ms
memory: 73144kb
input:
50 12 45 45 50 24 45 45 5 50 50 24 24 45 31 5 9 24 24 31 24 24 12 45 5 12 12 32 45 9 45 32 31 5 50 12 32 24 50 5 9 32 50 9 31 9 9 32 31 50 45
output:
14 14
result:
ok single line: '14 14'
Test #11:
score: 0
Accepted
time: 190ms
memory: 73184kb
input:
50 42 32 42 42 42 42 42 32 42 32 42 42 42 42 42 42 32 32 32 32 42 42 32 32 42 32 42 32 42 42 32 32 42 32 32 32 42 32 32 32 32 42 42 32 32 42 32 42 32 42
output:
0 3
result:
ok single line: '0 3'
Test #12:
score: 0
Accepted
time: 49ms
memory: 71136kb
input:
50 47 47 12 38 43 9 12 49 47 47 38 43 47 43 37 38 9 12 38 38 47 37 9 9 37 38 38 12 47 12 12 24 49 43 43 43 49 49 47 43 38 24 47 47 43 9 12 37 9 12
output:
0 7
result:
ok single line: '0 7'
Test #13:
score: 0
Accepted
time: 62ms
memory: 73260kb
input:
50 2 40 16 35 7 38 40 40 40 7 16 7 40 2 38 16 16 38 2 38 40 2 40 2 40 7 2 2 2 40 2 38 40 38 16 35 2 2 38 40 7 7 7 2 2 16 40 38 2 7
output:
0 6
result:
ok single line: '0 6'
Test #14:
score: 0
Accepted
time: 49ms
memory: 73332kb
input:
50 37 37 36 15 13 13 36 36 13 13 35 36 36 3 13 29 37 36 36 21 35 13 35 35 36 21 15 15 36 37 37 21 37 21 21 29 3 3 35 36 29 29 3 36 36 3 3 35 15 21
output:
0 5
result:
ok single line: '0 5'
Test #15:
score: 0
Accepted
time: 39ms
memory: 71200kb
input:
50 37 9 8 16 16 9 9 30 36 6 37 16 23 30 8 50 1 9 16 1 23 23 1 1 22 38 38 16 1 37 8 16 1 9 9 8 8 1 22 30 22 23 37 6 36 30 8 50 1 22
output:
0 9
result:
ok single line: '0 9'
Test #16:
score: 0
Accepted
time: 133ms
memory: 71460kb
input:
50 5 5 5 5 5 5 5 5 5 5 5 5 3 3 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5 4 4 5
output:
0 2
result:
ok single line: '0 2'
Test #17:
score: 0
Accepted
time: 19ms
memory: 73332kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 47 24 1 49 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
6 25
result:
ok single line: '6 25'
Test #18:
score: 0
Accepted
time: 15ms
memory: 71564kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 47 24 1 2 47 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
0 25
result:
ok single line: '0 25'
Test #19:
score: 0
Accepted
time: 39ms
memory: 71212kb
input:
50 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5
output:
0 14
result:
ok single line: '0 14'
Test #20:
score: 0
Accepted
time: 52ms
memory: 73336kb
input:
50 1 3 5 7 9 11 3 7 3 9 11 1 5 1 1 9 7 7 3 5 3 7 11 9 5 7 1 3 11 5 9 3 5 11 9 1 11 5 1 7 7 3 9 11 9 3 5 11 9 7
output:
4 8
result:
ok single line: '4 8'