当前位置:网站首页>Easy to understand subset DP
Easy to understand subset DP
2022-04-23 09:34:00 【Zimba_】
Pre knowledge :
Pressure :
In binary ( or n Base number ) Represents the decimal number to represent the State , State adjustment through bit operation .
for instance , In the room 4 The light turns on and off as 0101, The decimal number stored in this state is 5.
Numbered from right to left 0,1,2,3. Open the first 3 The lamp is about to be in its original state 5 Turn into 5|(1<<3).
Only a brief introduction is made to the shape pressure .
Enumerate binary subsets :
Binary numbers are s, Enumerating its subsets means , Enumerate all x∈{x| x|s=s}.
The specific operation is as follows :
for (int i = s; i; i = (i - 1) &s)
In this way, we can accurately enumerate s Binary subset of , Note that the neutron set of the cycle body does not contain 0( An empty set ), To add , Cycle conditions need to be set manually .
Text :
summary :
seeing the name of a thing one thinks of its function , A subset of dp State transition of , It is usually transferred from the subset to the current set , With the enumeration method of enumerating binary subsets , The code will be very comfortable to write , Can have better complexity .
frame :
Transfer equation dp[S]=dp[S⊕T]+max(dp[T]),T⊆S And T≠Ø For example , among S⊕T The meaning is T About S The complement of , The general framework is as follows .
for(int i=0;i<1<<n;i++)
{
for(int j=S&(S-1);j;S&(j-1))
{
dp[S]=max(dp[S],dp[S^j]+dp[j]);
}
}
Proof of complexity :
Enumerate subsets of all collections .
∑ i = 0 n ( n i ) 2 i = 3 n \sum_{i=0}^{n}\binom{n}{i}2^{i}= 3^{n} ∑i=0n(in)2i=3n
That is to say o(3n).
Example ( The bullock practice match 49B):
A brief description of the problem : this is it
AC Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int p[20];
int plan[1<<20];
int dp[1<<20];
int num[1<<20];
int gt(int x)
{
if(x==0)return 0;
if(num[x])return num[x];
int ans=0;
int t=x;
while(t!=0)
{
ans++;
t-=t&-t;
}
return num[x]=ans;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int sum=0;
for(int i=0;i<n;i++)scanf("%d",&p[i]),sum+=p[i];
sort(p,p+n,greater<int>());
for(int i=1;i<=m;i++)
{
int tn;
scanf("%d",&tn);
int x=0;
for(int j=1;j<=tn;j++)
{
int w;
scanf("%d",&w);
x|=1<<w-1;
}
plan[x]=1;
}
dp[0]=0;
for(int i=1;i<1<<n;i++)
{
for(int j=i&(i-1);1;j=i&(j-1))
{
int e=0;
if(plan[i^j])e=p[gt(i)-1];
else e=0;
dp[i]=max(dp[i],dp[j]+e);
if(j==0)break;
}
}
printf("%d\n",sum-dp[(1<<n)-1]);
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425917.html
边栏推荐
- kernel-pwn学习(3)--ret2user&&kernel ROP&&QWB2018-core
- Three ways to create objects in JS
- NLLLoss+log_ SoftMax=CE_ Loss
- Applet error: cannot read property'currenttarget'of undefined
- DVWA range practice record
- ALV树(LL LR RL RR)插入删除
- Installation of data cleaning ETL tool kettle
- Redis 内存占满导致的 Setnx 命令执行失败
- Get trustedinstaller permission
- RSA encryption and decryption signature verification
猜你喜欢
653. Sum of two IV - input BST
AI上推荐 之 MMOE(多任务yyds)
Flink SQL realizes the integration of stream and batch
What is monitoring intelligent playback and how to use intelligent playback to query video recording
SAP CR transmission request sequence and dependency check
Acquisition of DOM learning elements JS
Redis 异常 read error on connection 解决方案
亚马逊云科技入门资源中心,从0到1轻松上云
Kernel PWN learning (4) -- double fetch & 0ctf2018 baby
Practice of Flink streaming batch integration in Xiaomi
随机推荐
3、 6 [Verilog HDL] gate level modeling of basic knowledge
Employee probation application (Luzhou Laojiao)
Three ways to create objects in JS
Kettle experiment (III)
Go language learning notes - structure | go language from scratch
ATSS(CVPR2020)
《信息系统项目管理师总结》第八章 项目干系人管理
Go language learning notes - array | go language from scratch
OpenCV中的图像处理 —— 轮廓入门+轮廓特征
重载、重写、隐藏的对比
Operation not allowed for a result set of type resultset TYPE_ FORWARD_ ONLY. Explain in detail
亚马逊云科技入门资源中心,从0到1轻松上云
Kettle experiment
112. Path sum
考研线性代数常见概念、问题总结
JSON input of Chapter 14 of kettle paoding jieniu
Three challenges that a successful Devops leader should be aware of
Kettle实验 (三)
Go language learning notes - language interface | go language from scratch
Comparison of overloading, rewriting and hiding