BZOJ2073 「POI2004」PRZ 状压DP

问题描述

BZOJ2073


题解

发现 \(n \le 16\) ,显然想到状压

\(opt[S]\) 代表过河集合为 \(S\) 时,最小时间。

枚举 \(S\) 的子集,进行转移


枚举子集的方法

对于 \(j\)\(k\) 的子集

当知道 \(j\)

for(int k=(j+1)|j;k<=S;k=(k+1)|j)

当知道 \(k\)

for(int j=(k-1)&k;j;j=(j-1)&k)

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=19;
const int INF=0x3f3f3f3f;

int mx,n;
int opt[1<<17];
int t[maxn],w[maxn];

pair<int,int> calc(int x,int y){
    int res1(0),res2(0);
    for(int i=1;i<=n;i++){
        int k=((x>>(i-1))&1),p=((y>>(i-1))&1);
        if(k==1&&p==0) res1+=w[i],res2=max(res2,t[i]);
    }
    return make_pair(res1,res2);
}

int main(){
    read(mx);read(n);
    for(int i=1;i<=n;i++){
        read(t[i]);read(w[i]);
    }
    memset(opt,0x3f,sizeof(opt));
    opt[0]=0;
    for(int i=1;i<(1<<n);i++){
        for(int j=(i-1)&i;1;j=(j-1)&i){
            int W,T;
            pair <int,int> pr=calc(i,j);
            W=pr.first,T=pr.second;
            if(W<=mx) opt[i]=min(opt[i],opt[j]+T);
            if(j==0) break;
        }
    }
    printf("%d\n",opt[(1<<n)-1]);
    return 0;
}
全部评论

相关推荐

06-07 21:26
江南大学 C++
话不多说,直接上时间线和图片1.2024年10月底发offer,并签三方2.2025年5月底公司违约
从零开始的转码生活:希望所有签了三方但直接违约的公司都倒闭!都倒闭!都倒闭!
点赞 评论 收藏
分享
牛客773130651号:巨佬,简历模板换成上下的,左右的很烦,hr看着不爽。。。科大随便乱杀,建议能保研就保研,不行也得考一下 ,985硕去干算法,比开发强多了。开发许多双非都能搞,学历优势用不上,算法有门槛
点赞 评论 收藏
分享
吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务