https://ac.nowcoder.com/acm/contest/331/H

题目可以理解为有n(5000)个物品，每个物品有价值a[i](1~1e9)，从中选择最少的物品，使得剩余物品的价值之和小于固定的值K(1~1e15)，求解决方案，如果有多个解决方案，则用1表示选择该物品，0表示未选择，组成一个长度为n的01串，给出字典序最小的串

刚开是看题目，知道是背包问题了,然而呢，然而接下来怎么做就完全不知道了。

看了看题解，

首先，可以求出来最少选择多少个物品，对的，直接选价值最大的物品就行了，得到物品数ans

这个ans非常有用，接下来的过程就要好好利用到ans，于是问题就变成了,找到解决方案，该解决方案使用ans个物品，且为选择的物品价值总和不超过K

定义dp[i][j]为使用在[i~n]个物品中选择[j]个物品，剩余物品的最小价值数

可以通过简单的dp算出dp[i][j]=min(dp[i+1][j]+a[i],dp[i+1][j-1])

于是我们可以这样想，从左到右扫描每个物品，能不选择该物品的时候我们就不选择该物品，这不也就是字典序最小的精髓么，能是0就是0，不得已就是1。

我们记录开始的价值和为C=0，开始选择了cnt=0个物品

如果前面i个物品选择cnt个的剩余价值和C+后面[i+1,n]的物品选择(ans-cnt)个的剩余价值和dp[i+1,ans-cnt] >K

那么第i个物品就非选择不可,

否则第i个物品就可以不选，那我们就不选

//Problem:
//Date:
//Skill:8_2-框架
//Bug:
/////////////////////////////////////////definations////////////////////
#define CLR(a) memset((a),0,sizeof(a))
#define RE(i,n)  for(ll i=0;i<n;i++)
#define RE2(i,n) for(int i=1;i<=n;i++)
#define IN(n) scanf("%d",&n)
#define LLIN(n) scanf("%lld",&n)
#define INC(c) do {scanf("%c",&c);}while(isspace(c))
#define PI(a) prllf("%d",a)
#define LLPI(a) prllf("%lld",a)
#define PN  puts("");
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
 
#define CPP_I/O
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
///////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////options////////////////////////////////
typedef long long ll;
const ll maxn = ll(5e3+4);
ll n,k;
ll a[maxn],b[maxn];
ll dp[maxn][maxn];
//ll num(0);
ll num(0),sum=0;
bool ans[maxn];
//#define LOCAL
///////////////////////////////////////////////////////////////////////////////
int main()
{
#ifdef LOCAL
 
//  freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
#endif
    //How to think:
    //先认真读题，把题目逻辑化，读清全部条件，再做，不然，哼哼
    //1.分治 2.容斥 3.化多元为单元
    //4.dp 分阶段，后阶段受前阶段的影响
    //5.凡是有很大的指数的，都可以先用log算一下
    //6.预处理，作用非常大，很快
    //
    //1.Do you use cout/cin? Do not use!
    //2.what's the maximum ll data? Is it beyond I32d?
    //3.Ever Mod after neccesary calculation?
    //4.Ever Cleaned the array before using?
    ///////////////////////////////////////////code////////////////////////////////
    ll T(1), times(0);
    //IN(T);
    while (++times,T--)
    {
        cin>>n>>k;num=n;
        RE2(i,n)cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
//      cout<<sum<<' '<<num<<endl;
//      for(ll i=n;i;--i)
        RE2(i,n)
        {
            sum+=b[i];
            if(sum<=k)
            {
                --num;
            }
            else break;
        }
//      cout<<sum<<' '<<num<<endl;
        for(ll i=n;i;--i)
        {
            dp[i][0]=dp[i+1][0]+a[i];
            for(ll j=num;j;--j)
            {  
                dp[i][j]=min(dp[i+1][j]+a[i],dp[i+1][j-1]);
            }
        }
         
        ll C=0,res(num);
        RE2(i,n)
        {
            if(C+a[i]+ dp[i+1][res]>k)
            {
                ans[i]=1;
                --res;
            }
            else
                C+=a[i],ans[i]=0;
        }
        cout<<n-num<<endl;
        RE2(i,n)cout<<ans[i];
        cout<<endl;
    }
    //////////////////////////////////////////////////////////////
    //dividing line
    return 0;
}