11-17 00:12 已编辑 深圳技师学院 C++ 发布于广东
关注
状压dp
对于一个集合，他一有2^n个子集，而状态压缩就是枚举这些子集，每一个状态就是一个由01构成的集合，如果为0就表示不选当前的元素，否则就表示选。因为状态压缩将每一个状态压缩成了一个用二进制表示的数，所以不光可以节省空间，还可以节省时间。
因为是枚举子集，所以时间复杂度为O(2^n)),一般使用的标志就是n≤20
代码:
#include
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 cnt(14);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
cnt[x]++;
}
vector sum(1<<13);
vector dp(1<<13,14);
//初始化
for(int i=1;i<(1<<13);i++) //枚举2的13次方的状态
{
for(int j=0;j<13;j++) //每个状态代表的值
{
if(i>>j&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)&i) //dp转移 该状态是从前一个状态转移而来 0101 从0001或0100转移
{
if(sum[j]>w) continue;
else
dp[i]=min(dp[i],dp[i-j]+1);
}
}
cout<
}#许愿池#
因为是枚举子集，所以时间复杂度为O(2^n)),一般使用的标志就是n≤20
代码:
#include
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
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
cnt[x]++;
}
vector
vector
//初始化
for(int i=1;i<(1<<13);i++) //枚举2的13次方的状态
{
for(int j=0;j<13;j++) //每个状态代表的值
{
if(i>>j&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)&i) //dp转移 该状态是从前一个状态转移而来 0101 从0001或0100转移
{
if(sum[j]>w) continue;
else
dp[i]=min(dp[i],dp[i-j]+1);
}
}
cout<
}#许愿池#
全部评论
相关推荐
查看14道真题和解析
点赞 评论 收藏
分享