QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #779659 | #5190. 小 E 爱消除 | ffffyc | AC ✓ | 263ms | 73340kb | C++14 | 3.4kb | 2024-11-24 20:52:27 | 2024-11-24 20:52:27 |
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;
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);
else if(l1>r1) tp=f[1][0][l2][r2];
else if(l2>r2) tp=f[l1][r1][r1+1][r1];
else tp=f[l1][r1][l2][r2];
if(tp.fir) tp=mpr(INF,INF);
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],mpr(1,1)+g[l+1][r]);
upd(g[l][r],mpr(1,1)+g[l][r-1]);
for(int k=l+1;k<=r;k++)
if(c[l]==c[k]){
for(int p=l+1;p<=k;p++)
upd(g[l][r],mpr(1,1)+F(l+1,p-1,k+1,r)+mpr(-1,1)+g[p][k-1]);
for(int p=k+1;p<=r;p++)
upd(g[l][r],mpr(1,1)+F(l+1,k-1,p+1,r)+mpr(-1,1)+g[k+1][p]);
}
for(int k=l;k<=r-1;k++)
if(c[r]==c[k]){
for(int p=k;p<=r-1;p++)
upd(g[l][r],mpr(1,1)+F(l,k-1,p+1,r-1)+mpr(-1,1)+g[k+1][p]);
for(int p=l;p<=k-1;p++)
upd(g[l][r],mpr(1,1)+F(l,p-1,k+1,r-1)+mpr(-1,1)+g[p][k-1]);
}
}
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));
for(int q=l2;q<=r2-1;q++)
if(c[r2]==c[q])
for(int p=l1-1;p<=r1;p++)
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));
}
}
}
write(g[1][n].fir),putc(' '),write(g[1][n].sec);
flush();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 178ms
memory: 71728kb
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: 131ms
memory: 71444kb
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: 62ms
memory: 73260kb
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: 41ms
memory: 71204kb
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: 18ms
memory: 71204kb
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: 5684kb
input:
1 1
output:
1 1
result:
ok single line: '1 1'
Test #7:
score: 0
Accepted
time: 263ms
memory: 73116kb
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: 52ms
memory: 71288kb
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: 55ms
memory: 73340kb
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: 46ms
memory: 71196kb
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: 184ms
memory: 71268kb
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: 47ms
memory: 73248kb
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: 61ms
memory: 71208kb
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: 50ms
memory: 71224kb
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: 33ms
memory: 73180kb
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: 128ms
memory: 71284kb
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: 71272kb
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: 71312kb
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: 71456kb
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: 71684kb
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'