QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694620#1444. PalindromeAfterlife#AC ✓15ms114548kbC++202.1kb2024-10-31 18:20:242024-10-31 18:20:28

Judging History

This is the latest submission verdict.

  • [2024-10-31 18:20:28]
  • Judged
  • Verdict: AC
  • Time: 15ms
  • Memory: 114548kb
  • [2024-10-31 18:20:24]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,a[N];
string s;
int dp[N][N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    cin>>s;
    int c0=0,c1=0;
    for(int i=1;i<=n;++i){
        a[i]=s[i-1]-'0';
        if(a[i]==0)++c0;
        else ++c1;
    }
    if(c0&1&&c1&1){
        cout<<-1<<'\n';
        return 0;
    }
    memset(dp,~0x3f,sizeof(dp));
    for(int i=1;i<=n;++i){
        if(c0&1){
            if(a[i]==0)dp[i][i][0]=1;
        }
        else if(c1&1){
            if(a[i]==1)dp[i][i][1]=0;
        }
        else{
            dp[i][i][0]=0;
        }
    }
    if(c0%2==0&&c1%2==0){
        for(int i=0;i<=n;++i){
            dp[i+1][i][0]=0;
        }
    }
    for(int len=2;len<=n;++len){
        for(int l=1;l+len-1<=n;++l){
            int r=l+len-1;
            for(int k=0;k<=len;++k){
                int &u=dp[l][r][k];
                u=max(dp[l+1][r][k],dp[l][r-1][k]);
            }
            if(a[l]==a[r]){
                if(a[l]==0){
                    for(int k=0;k<=len;++k){
                        dp[l][r][k]=max(dp[l][r][k],dp[l+1][r-1][k]+2);
                    }
                }
                else{
                    for(int k=2;k<=len;++k){
                        dp[l][r][k]=max(dp[l][r][k],dp[l+1][r-1][k-2]);
                    }
                }
            }
            // for(int k=0;k<=len;++k){
            //     if(dp[l][r][k]>=0){
            //         cerr<<" ... "<<l<<" "<<r<<" "<<dp[l][r][k]<<" "<<k<<endl;
            //     }
            // }
        }
    }
    int ans=n/2;
    int d0=0,d1=0;
    for(int i=0;i<=n;++i){
        if(i>0){
            if(a[i]==0)++d0;
            else ++d1;
        }
        for(int z1=0;z1<=n;++z1){
            int z0=dp[i+1][n][z1];
            if(z0<0)continue;
            int p=c0-z0;
            int q=c1-z1;
            if(p&1||q&1)continue;
            if(d0<p/2||d1<q/2)continue;
            ans=max(ans,p/2+q/2+z0+z1);
        }
    }
    cout<<n-ans<<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 114488kb

input:

7
1101001

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 7ms
memory: 114500kb

input:

4
1001

output:

0

result:

ok "0"

Test #3:

score: 0
Accepted
time: 8ms
memory: 114540kb

input:

12
110100010011

output:

3

result:

ok "3"

Test #4:

score: 0
Accepted
time: 0ms
memory: 114416kb

input:

19
0010010101110111101

output:

4

result:

ok "4"

Test #5:

score: 0
Accepted
time: 8ms
memory: 114476kb

input:

46
0011000100001111001000010000000001100011101100

output:

8

result:

ok "8"

Test #6:

score: 0
Accepted
time: 7ms
memory: 114476kb

input:

34
0111010110110110011011110001100011

output:

6

result:

ok "6"

Test #7:

score: 0
Accepted
time: 7ms
memory: 114488kb

input:

16
1010000101001010

output:

3

result:

ok "3"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

50
10101101001100100110111010001001010001011001101011

output:

-1

result:

ok "-1"

Test #9:

score: 0
Accepted
time: 3ms
memory: 114488kb

input:

32
01111001100011100110111111101111

output:

8

result:

ok "8"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

14
01101101011101

output:

-1

result:

ok "-1"

Test #11:

score: 0
Accepted
time: 4ms
memory: 114412kb

input:

48
101010011000111111001111101111100111110101101101

output:

6

result:

ok "6"

Test #12:

score: 0
Accepted
time: 3ms
memory: 114408kb

input:

29
10111101101100111100110011101

output:

4

result:

ok "4"

Test #13:

score: 0
Accepted
time: 0ms
memory: 114492kb

input:

17
01111001010010101

output:

3

result:

ok "3"

Test #14:

score: 0
Accepted
time: 11ms
memory: 114408kb

input:

134
00100101011101111010001101000111101110011001111110100101010011001010000001011111000000001110101010100010010110111011001011000010110010

output:

18

result:

ok "18"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

114
001100010000111100100001000000000110001110110001111001100000101100010010110001001001010010111110101000010101111011

output:

-1

result:

ok "-1"

Test #16:

score: 0
Accepted
time: 7ms
memory: 114408kb

input:

97
0111010110110110011011110001100011010110000100111110000011001101011100100010000110010011011100110

output:

18

result:

ok "18"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

78
101000010100101001100100010110101110110100111000101011111101111010000001101111

output:

-1

result:

ok "-1"

Test #18:

score: 0
Accepted
time: 0ms
memory: 114416kb

input:

61
1010110100110010011011101000100101000101100110101110110000011

output:

8

result:

ok "8"

Test #19:

score: 0
Accepted
time: 7ms
memory: 114416kb

input:

193
0111100110001110011011111110111111111110101001001110101001111101001101101000100010011010000111001101011000110000110101100011110100111001111000000001110000011000011001101011100010111111111001111

output:

32

result:

ok "32"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

174
011011010111011101100101101111000100011100000111101010011111101001000110001101011001101101001001010001110001000000000111100010111001011110010011000011011001000000010101011000

output:

-1

result:

ok "-1"

Test #21:

score: 0
Accepted
time: 7ms
memory: 114420kb

input:

157
1010100110001111110011111011111001111101011011011010111010101001111101011111010001001101100111011100110000010001011001100010111000100110101110101010001010100

output:

27

result:

ok "27"

Test #22:

score: 0
Accepted
time: 9ms
memory: 114544kb

input:

137
10111101101100111100110011101101101001101100111111101000011001111001010101001001010010001000100001011111000000010101111100011110000000001

output:

25

result:

ok "25"

Test #23:

score: 0
Accepted
time: 3ms
memory: 114492kb

input:

120
011110010100101011000110101010110001111111100000101010010110000001100111101011001001101001000110010001110000001000101110

output:

20

result:

ok "20"

Test #24:

score: 0
Accepted
time: 4ms
memory: 114484kb

input:

255
001001010111011110100011010001111011100110011111101001010100110010100000010111110000000011101010101000100101101110110010110000101100101111000000001111100110000110001010111101011010000100011000110000001101011011100010101010011100101001111011001001101110010

output:

36

result:

ok "36"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

256
0011000100001111001000010000000001100011101100011110011000001011000100101100010010010100101111101010000101011110110000110110010101011111010110100011110101010000000101011001010010110000011110101110111010100111010010010110010011111100010110111001001010011001

output:

-1

result:

ok "-1"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

292
0111010110110110011011110001100011010110000100111110000011001101011100100010000110010011011100110011001001101110111100100101010101111110001110010000111111010001011000100010111000100101100110001110000000000101010001010110011010111000101110101100000110000011100100001100100101001010010001001010

output:

-1

result:

ok "-1"

Test #27:

score: 0
Accepted
time: 11ms
memory: 114536kb

input:

294
101000010100101001100100010110101110110100111000101011111101111010000001101111000100000110100101101011100110111110011111111010001100100000010100000010001110100011101111011110101011001101101010110001000111101011111110001010111010110010011100110001001111000101010100111101000011110001111101010010

output:

45

result:

ok "45"

Test #28:

score: 0
Accepted
time: 4ms
memory: 114424kb

input:

229
1010110100110010011011101000100101000101100110101110110000011001110100010100110101001100110100000010110101101111111011110000110001101001011011110011101101101001111110001000100000100010100010011110101111011000111100001110111010111

output:

39

result:

ok "39"

Test #29:

score: 0
Accepted
time: 4ms
memory: 114480kb

input:

231
011110011000111001101111111011111111111010100100111010100111110100110110100010001001101000011100110101100011000011010110001111010011100111100000000111000001100001100110101110001011111111100111111100011000111101011001111100101101011

output:

42

result:

ok "42"

Test #30:

score: 0
Accepted
time: 0ms
memory: 114496kb

input:

233
01101101011101110110010110111100010001110000011110101001111110100100011000110101100110110100100101000111000100000000011110001011100101111001001100001101100100000001010101100000001111110000010100010101001011110101011100110001110000011

output:

33

result:

ok "33"

Test #31:

score: 0
Accepted
time: 4ms
memory: 114420kb

input:

269
10101001100011111100111110111110011111010110110110101110101010011111010111110100010011011001110111001100000100010110011000101110001001101011101010100010101000011001101000010110101010001100011100111011010111001110010001011100010001011011001000110110010111010111100010000

output:

45

result:

ok "45"

Test #32:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

270
101111011011001111001100111011011010011011001111111010000110011110010101010010010100100010001000010111110000000101011111000111100000000011010101101100001010000010001111101101100111100100100100001101001011001011101000110110010001000100010011001010110010011000011110110110

output:

-1

result:

ok "-1"

Test #33:

score: 0
Accepted
time: 4ms
memory: 114424kb

input:

205
0111100101001010110001101010101100011111111000001010100101100000011001111010110010011010010001100100011100000010001011101011101111010001010001101001011100011001110100001100111001101101010001100001001010000

output:

34

result:

ok "34"

Test #34:

score: 0
Accepted
time: 15ms
memory: 114460kb

input:

299
00100101011101111010001101000111101110011001111110100101010011001010000001011111000000001110101010100010010110111011001011000010110010111100000000111110011000011000101011110101101000010001100011000000110101101110001010101001110010100111101100100110111001001010101101000101100110101001111111010101...

output:

49

result:

ok "49"

Test #35:

score: 0
Accepted
time: 15ms
memory: 114420kb

input:

300
00110001000011110010000100000000011000111011000111100110000010110001001011000100100101001011111010100001010111101100001101100101010111110101101000111101010100000001010110010100101100000111101011101110101001110100100101100100111111000101101110010010100110011100111100111101100111000000011010110000...

output:

50

result:

ok "50"

Test #36:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

300
01110101101101100110111100011000110101100001001111100000110011010111001000100001100100110111001100110010011011101111001001010101011111100011100100001111110100010110001000101110001001011001100011100000000001010100010101100110101110001011101011000001100000111001000011001001010010100100010010101110...

output:

-1

result:

ok "-1"

Test #37:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

300
10100001010010100110010001011010111011010011100010101111110111101000000110111100010000011010010110101110011011111001111111101000110010000001010000001000111010001110111101111010101100110110101011000100011110101111111000101011101011001001110011000100111100010101010011110100001111000111110101001011...

output:

-1

result:

ok "-1"

Test #38:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

300
10101101001100100110111010001001010001011001101011101100000110011101000101001101010011001101000000101101011011111110111100001100011010010110111100111011011010011111100010001000001000101000100111101011110110001111000011101110101110100101010110010010100010010011000000101000011110110111100100010111...

output:

-1

result:

ok "-1"

Test #39:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

300
01111001100011100110111111101111111111101010010011101010011111010011011010001000100110100001110011010110001100001101011000111101001110011110000000011100000110000110011010111000101111111110011111110001100011110101100111110010110101110111010111100101001101111111000101001001101001111010001001110011...

output:

-1

result:

ok "-1"

Test #40:

score: 0
Accepted
time: 8ms
memory: 114476kb

input:

300
01101101011101110110010110111100010001110000011110101001111110100100011000110101100110110100100101000111000100000000011110001011100101111001001100001101100100000001010101100000001111110000010100010101001011110101011100110001110000011101001001110001010011011011110101110101110100011010001111011010...

output:

44

result:

ok "44"

Test #41:

score: 0
Accepted
time: 15ms
memory: 114404kb

input:

300
10101001100011111100111110111110011111010110110110101110101010011111010111110100010011011001110111001100000100010110011000101110001001101011101010100010101000011001101000010110101010001100011100111011010111001110010001011100010001011011001000110110010111010111100010000001000100111101101110001100...

output:

48

result:

ok "48"

Test #42:

score: 0
Accepted
time: 4ms
memory: 114476kb

input:

299
10111101101100111100110011101101101001101100111111101000011001111001010101001001010010001000100001011111000000010101111100011110000000001101010110110000101000001000111110110110011110010010010000110100101100101110100011011001000100010001001100101011001001100001111011011000011001011100101011100001...

output:

54

result:

ok "54"

Test #43:

score: 0
Accepted
time: 8ms
memory: 114548kb

input:

299
01111001010010101100011010101011000111111110000010101001011000000110011110101100100110100100011001000111000000100010111010111011110100010100011010010111000110011101000011001110011011010100011000010010100000010000001110011101001101110001100101111101010111001100101001100100001100100000000000110101...

output:

51

result:

ok "51"

Test #44:

score: 0
Accepted
time: 4ms
memory: 114412kb

input:

1
1

output:

0

result:

ok "0"

Test #45:

score: 0
Accepted
time: 0ms
memory: 114544kb

input:

1
0

output:

0

result:

ok "0"

Test #46:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2
10

output:

-1

result:

ok "-1"

Test #47:

score: 0
Accepted
time: 3ms
memory: 114460kb

input:

2
11

output:

0

result:

ok "0"

Test #48:

score: 0
Accepted
time: 0ms
memory: 114492kb

input:

3
111

output:

0

result:

ok "0"

Test #49:

score: 0
Accepted
time: 3ms
memory: 114412kb

input:

5
10000

output:

3

result:

ok "3"

Test #50:

score: 0
Accepted
time: 7ms
memory: 114492kb

input:

9
000000001

output:

4

result:

ok "4"

Test #51:

score: 0
Accepted
time: 0ms
memory: 114492kb

input:

5
11100

output:

3

result:

ok "3"