题解：P15962 [ICPC 2018 Jakarta R] Binary String

Cpp__5417__ · 2026-04-26 08:35:03 · 题解

P15962 [ICPC 2018 Jakarta R] Binary String题解

一道 DP 好题，但也可以用贪心做。

Problem

题目的意思就是说有一个二进制串 S，要删除尽量少的二进制位，使其转换为十进制后的数 \le⁡K，且删除后最高位为 1。

Solution

既然说删除尽量少的二进制位，那等价于保留尽量多的二进制位。

题目中又说删除后最高位要为 1，那么可以枚举删除后的二进制串 S 的第 i 位 S_i，求以 S_i 开头的二进制串长度的最大值。

那怎么求呢？DP。

设 f_j 为在以当前位的下一位为开头（可包含前导 0）时保留 j 个二进制位时的最小值，初始化 f_0=0，其余 f_j=\infin。

然后用 j 变量遍历 S_{i+1\dots⁡n-1}，每遍历一个字符对整个 f 进行更新，转移方程：

DP 完之后，可得实际最大值为 \max\limits_{j=1}^{n-i-1}⁡{2^j+f_j}，其中 2^j 表示加上最高位，注意判断 2^j+f_j\le⁡k。

本题 n\le⁡60⁡，完全可行。

Code

:::success[AC of C++]

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define BINF 0x7f
#define int __long_long
#define db double
#define i64 __int128
#define cauto const auto
#define Int signed
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b/gcd(a,b))
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long __long_long;
typedef pair<int,int> pii;
int k,n,r;
string s;
int f[38<<1];
void Cpp(){
    cin>>k>>s;
    n=s.size();
    for(int i=0;i<n;i++)if(s[i]=='1'){
        fill(f,f+n-i,INF);
        f[0]=0;
        for(int j=i+1;j<n;j++){
            int b=s[j]^'0';//优化，即 s[j]-'0'
            for(int c=n-i-1;c>0;c--){
                int val=(f[c-1]<<1)|b;//即 f[c-1]*2+b
                if(val<=k)f[c]=min(f[c],val);
            }
        }
        for(int c=0;c<=n-i-1;c++){
            if(f[c]<=k){
                int v=(1ll<<c)|f[c];
                if(v<=k)r=max(r,c+1);
            }
        }
    }
    printf("%lld\n",n-r);
}
signed main(){
    int q=1;
//  cin>>q;
    while(q--){Cpp();}
    return 38&17;
}

::: :::success[AC of Python]

k=int(input())
r=0
s=input()
f=[0 for _ in range(38<<1)]
n=len(s)
for i in range(n):
    if(s[i]=='1'):
        for j in range(n-i):f[j]=2<<61
        f[0]=0
        for j in range(i+1,n):
            b=int(s[j])
            for c in range(n-i-1,0,-1):
                val=(f[c-1]<<1)|b# 即 f[c-1]*2+b
                if(val<=k):f[c]=min(f[c],val)
        for c in range(n-i):
            if(f[c]<=k):
                val=(1<<c)|f[c]
                if(val<=k):r=max(r,c+1)
        # print(*(f[0:n]))
print(n-r)

::: :::success[AC of Java]

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        long k=scan.nextLong();
        String s=scan.next();
        int n=s.length();
        long r=0;
        long f[]=new long[38<<1];
        for(int i=0;i<n;i++)if(s.charAt(i)=='1'){
            Arrays.fill(f,0,n-i,1l<<61);
            f[0]=0l;
            for(int j=i+1;j<n;j++){
                long b=s.charAt(j)^'0';//优化，即 s.charAt(j)-'0'
                for(int c=n-i-1;c>0;c--){
                    long val=(f[c-1]<<1)|b;//即 f[c-1]*2+b
                    if(val<=k)f[c]=Math.min(f[c],val);
                }
            }
            for(int c=0;c<=n-i-1;c++){
                if(f[c]<=k){
                    long v=(1l<<c)|f[c];
                    if(v<=k)r=Math.max(r,c+1);
                }
            }
        }
        System.out.println(n-r);
    }
}

:::

最后，这是本蒟蒻的第 3 篇题解，所以——点个赞呗。