[HDU6371]Chopping hands

Link

Solution

在有序表里删除点可以方便地维护中位数,所以初始全部插入然后DFS枚举删除哪些。

先按照pack大小排序可以强力加速。

然而HDOJ太慢还是T了。

然后spice的参数顺序!
a.splice(iter_a,b,iter_b)是把ba里搞!

Code

const int XN=30,XM=211;

std::vector<int> pack[XN];

int w[XM][XM],c[XN],n;
long long Ans,succs[XN],cost;

std::list<int> a,temp;
std::vector<std::list<int>::iterator> it[XM];
std::pair<std::list<int>::iterator,int> med;
std::vector<std::pair<int,std::pair<int,int>>> nums;

int cnt[XM];

int ord[XN];

void DFS(int p=1) {
    //std::cerr<<p<<','<<cost<<'\n';
    if(nums[a.back()].first*2-(cost+succs[p])<Ans)
        return;
    if(p==n+1)
        Enlarge(Ans,(a.size()&1?2*nums[(*med.first)].first
                    :nums[(*med.first)].first+nums[(*std::next(med.first))].first)-cost);
    else {
        cost+=c[ord[p]];
        DFS(p+1);
        cost-=c[ord[p]];
        if(!(p==n && cost==0)) {
            static std::pair<int,std::list<int>::iterator> stack[XM];
            static int top;
            auto backup=med;
            int pre=top;
            for(auto x : pack[ord[p]]) {
                stack[++top]={x,std::next(it[x][cnt[x]])};
                if(*it[x][cnt[x]]<*med.first)
                    med.second--;
                else if(*it[x][cnt[x]]==*med.first)
                    med.first++;
                temp.splice(temp.end(),a,it[x][cnt[x]--]);
                while(med.second<(int)(a.size()+1)/2) {
                    ++med.first;
                    ++med.second;
                }
                while(med.second>(int)(a.size()+1)/2) {
                    --med.first;
                    --med.second;
                }
            }
            DFS(p+1);
            med=backup;
            for(;top!=pre;top--)
                a.splice(stack[top].second,temp,it[stack[top].first][++cnt[stack[top].first]]);
        }
    }
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        //std::cerr<<T<<'\n';
        int m;std::cin>>n>>m;
        for(int i=1;i<=n;++i)
            std::cin>>c[i];
        for(int i=1;i<=m;++i)
            cnt[i]=0;
        for(int i=1;i<=n;++i) {
            int k;std::cin>>k;
            pack[i].resize(k);
            for(int j=0;j<k;++j) {
                std::cin>>pack[i][j];
                cnt[pack[i][j]]++;
            }
            ord[i]=i;
        }
        std::sort(ord+1,ord+1+n,[&](int x,int y)->bool {
            return pack[x].size()>pack[y].size();
        });
        succs[n+1]=0;
        for(int i=n;i>=1;--i)
            succs[i]=succs[i+1]+std::min(0,c[ord[i]]);
        a.clear();
        nums.clear();
        for(int i=1;i<=m;++i) {
            int k;std::cin>>k;
            it[i].resize(k+1);
            for(int j=1;j<=k;++j) {
                std::cin>>w[i][j];
                nums.push_back({w[i][j],{i,j}});
            }
        }
        std::sort(nums.begin(),nums.end());
        for(auto &p : nums)
            it[p.second.first][p.second.second]=a.insert(a.end(),a.size());

        med.first=a.begin();
        std::advance(med.first,(med.second=(a.size()+1)/2)-1);

        Ans=-1e18;
        cost=0;
        DFS();
        assert(temp.empty());
        std::cout<<Ans<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注