• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

1周前 (05-01) 5次浏览

# Two Pointers Method Step3 I.Segment with the Required Subset 双指针 + 01布尔背包 + 两个栈维护

## 题意

[1 leq n leq 10^5\
1 leq s leq 10^3\
1leq a_i leq s\
]

## 代码

``````#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),x.end()

using namespace std;
typedef long long ll;

ll rd(){
ll x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}

struct Stk{
vector<int> stk;
vector<bitset<1005>> bit;
void init(){
bitset<1005> tmp;
tmp[0] = 1;
bit.push_back(tmp);
}
void push(int x){
stk.push_back(x);
bitset<1005> tmp = bit.back();
bit.push_back(tmp | (tmp << x));
}
int top(){
return stk.back();
}
bitset<1005> get(){
return bit.back();
}
void pop(){
stk.pop_back();
bit.pop_back();
}
bool empty(){
return stk.empty();
}
}s1,s2;

s2.push(x);
}

void del(){
if(s1.empty()) {
while(!s2.empty())
s1.push(s2.top()),s2.pop();
}
s1.pop();
}

int s;
int n;

int a[100005];

bool good(){
bitset<1005> v1 = s1.get();
bitset<1005> v2 = s2.get();
for(int i = 0;i <= s;i++){
if(v1[i] && v2[s - i])
return 1;
}
return 0;
}

int main(){
s1.init();
s2.init();
n = rd();
s = rd();
for(int i = 1;i <= n;i++){
a[i] = rd();
}
int l = 1;
int ans = 1e9;
for(int i = 1;i <= n;i++){