QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #779657 | #5190. 小 E 爱消除 | ffffyc | WA | 191ms | 73196kb | C++14 | 3.4kb | 2024-11-24 20:50:36 | 2024-11-24 20:50:37 |
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],g[l+1][r]+mpr(1,1));
upd(g[l][r],g[l][r-1]+mpr(1,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();
}
详细
Test #1:
score: 100
Accepted
time: 191ms
memory: 71104kb
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: 136ms
memory: 71148kb
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: -100
Wrong Answer
time: 63ms
memory: 73196kb
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 7
result:
wrong answer 1st lines differ - expected: '2 8', found: '2 7'