状压dp

对于一个集合,他一有2^n个子集,而状态压缩就是枚举这些子集,每一个状态就是一个由01构成的集合,如果为0就表示不选当前的元素,否则就表示选。因为状态压缩将每一个状态压缩成了一个用二进制表示的数,所以不光可以节省空间,还可以节省时间。
因为是枚举子集,所以时间复杂度为O(2^n)),一般使用的标志就是n≤20

代码:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
   
    int n,w;
    cin>>n>>w;
    vector<int> cnt(14);
    for(int i=1;i<=n;i++)
    {
    int x;
    cin>>x;
    cnt[x]++;
}
vector<int> sum(1<<13);
vector<int> dp(1<<13,14);
    //初始化
for(int i=1;i<(1<<13);i++) //枚举2的13次方的状态
{
for(int j=0;j<13;j++) //每个状态代表的值
{
if(i>>j&amp;1) sum[i]+=cnt[j+1];
}
}
dp[0]=0;
for(int i=1;i<(1<<13);i++) //枚举每个状态
{
for(int j=i;j;j=(j-1)&amp;i) //dp转移 该状态是从前一个状态转移而来 0101 从0001或0100转移
{
if(sum[j]>w) continue;
else
dp[i]=min(dp[i],dp[i-j]+1);
}
}

cout<<dp[(1<<13)-1]<<endl;
return 0;
}#许愿池#
全部评论

相关推荐

程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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