【BZOJ1082】【SCOI2005】栅栏

爆搜出奇迹骗分过样例？

二分搜索+花式剪枝即可AC

太玄学了不是很懂

// <1082.cpp> - Wed Mar  8 09:18:15 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=1010;
const int INF=1e9;
int n,m,a[MAXN],b[MAXN],sa,sb[MAXN];
bool dfs(int x,int t,int s,int w){
    if(!t)return 1;
    if(w<0)return 0;
    for(int i=max(x,s);i<=n;i++){
        if(a[i]<b[t])continue;
        a[i]-=b[t];
        bool g;
        if(a[i]<b[1]){
            swap(a[i],a[n--]);
            g=dfs(x,t-1,(b[t]==b[t-1])*i,w-a[n+1]);
            swap(a[i],a[++n]);
        }else g=dfs(x,t-1,(b[t]==b[t-1])*i,w);
        a[i]+=b[t];
        if(g)return 1;
    }
    return 0;
}
int main(){
    n=gi();
    for(int i=1;i<=n;i++)sa+=(a[i]=gi());
    m=gi();
    for(int i=1;i<=m;i++)b[i]=gi();
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++)sb[i]=sb[i-1]+b[i];
    int l=0,r=m;
    while(l<r){
        int m=l+r+1>>1;
        if(dfs(1,m,0,sa-sb[m]))l=m;
        else r=m-1;
    }
    printf("%d",l);
    return 0;
}

// <1082.cpp> - Wed Mar 8 09:18:15 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=1010;

const int INF=1e9;

int n,m,a[MAXN],b[MAXN],sa,sb[MAXN];

bool dfs(int x,int t,int s,int w){

if(!t)return 1;

if(w<0)return 0;

for(int i=max(x,s);i<=n;i++){

if(a[i]<b[t])continue;

a[i]-=b[t];

bool g;

if(a[i]<b[1]){

swap(a[i],a[n--]);

g=dfs(x,t-1,(b[t]==b[t-1])*i,w-a[n+1]);

swap(a[i],a[++n]);

}else g=dfs(x,t-1,(b[t]==b[t-1])*i,w);

a[i]+=b[t];

if(g)return 1;

}

return 0;

}

int main(){

n=gi();

for(int i=1;i<=n;i++)sa+=(a[i]=gi());

m=gi();

for(int i=1;i<=m;i++)b[i]=gi();

sort(a+1,a+n+1);

sort(b+1,b+m+1);

for(int i=1;i<=m;i++)sb[i]=sb[i-1]+b[i];

int l=0,r=m;

while(l<r){

int m=l+r+1>>1;

if(dfs(1,m,0,sa-sb[m]))l=m;

else r=m-1;

}

printf("%d",l);

return 0;

}