[GN] DP学习笔记板子

---

Bitset

使用bitset需要引用<bitset>头文件。

其声明方法为:

std::bitset<N>s;  (N为s长度)

常用函数：

b.any()			判断b中是否存在值为1的二进制位
b.none()		判断b中是否不存在值为1的二进制位
b.count()		判断b中值为1的二进制位个数
b.size()		判断b中二进制位的个数
b[pos]			访问b中在pos处的二进制位
b.test(pos)		判断b中在pos处的二进制位是否为1
b.set()			把b中所有二进制位都置为1
b.set(pos)		把b[pos]置为1
b.reset()		把b中所有二进制位都置为0
b.reset(pos)	把b[pos]置为0
b.flip()		把b中所有二进制位逐位取反
b.flip(pos)		把b[pos]取反

滚动数组

   	memset(dp, inf, sizeof(dp)) ;dp[0][N]=0;for(int k = 1, i = 1; i <= n; i ++, k ^= 1){memset(dp[k], inf, sizeof(dp[k])) ;for(int j = -5000; j <= 5000; j ++)dp[k][j + N] = min(dp[k ^ 1][j + c[i] + N], dp[k ^ 1][j - c[i] + N] + 1) ;}int ans;for(int i=0;i<=5000;i++){ans=min(dp[n&1][i+N],dp[n&1][-i+N]);if(ans<1000) break;}

多重背包

       //分堆过程while(k<=s){//小于等于和小于都可以,因为如果出现等于的情况就是s=2^(k+1)-1,下面的if判断会处理掉cnt++;//cnt先++=>下标从1开始w[cnt] = k * wi;//k个物品为一堆v[cnt] = k * vi;s-=k;k*=2;}if(s>0){//如果存在最后一个堆cnt ++;//最后一个堆有s'个i物品w[cnt] = s * wi;v[cnt] = s * vi;}}n = cnt;//物品由n个变成了nlogs个 别忘了这句

区间DP

    for (int len = 1; len <= n; len++) {         // 区间长度for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点int j = i + len - 1;                 // 区间终点if (len == 1) {dp[i][j] = 初始值continue;}for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);}}}

树形dp

void dfs(int u,int fa){for(int i=0;i<g[u].size();i++){int v = g[u][i];if(v==fa) continue;dfs(v,u);for(int k=m;k>=0;k--)for(int j=1;j<=k;j++)dp[u][k] = max(dp[u][k],dp[u][k-j]+dp[v][j]);}for(int i=m;i>=1;i--){dp[u][i] = dp[u][i-1] + w[u];}}

状压dp

f[0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {f[mask] = min(f[mask], f[mask ^ (1 << i)] + (nums1[__builtin_popcount(mask) - 1] ^ nums2[i]));}}
}return f[(1 << n) - 1];int f[17][1<<17];
int dfs(int x,int y){if(f[x][y])return f[x][y];int ans=0;for(auto i:v[st[x][st[x].size()-1]])if(!((y>>(i-1))&1))ans=max(ans,dfs(i,y|(1<<(i-1))));return f[x][y]=ans+st[x].size();
}for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);for(int i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));1.是方格图求状态数、最大最小值。这种题一般是把每一行/列看做一个状态来转移的。预处理出每一行的所有状态，然后根据状态转移方程进行转移。该状态左右不相邻： !(i& i<< 1) 2.给你一个集合，然后每次从中选出一个数，选过的数不能再选dp[st] += dp[st^(1<<(i-1))]     (st&(1<<(i-1)) != 0)

模拟退火

const double eps=1e-18;
const double delta=0.999;//调了一年的参数一般为0.97~1.0class Solution {
public:vector<int> a,b;int ans=INT_MAX;//答案double fun(){int res=0;for(int i=0;i<a.size();i++)res+=(a[i]^b[i]);ans=min(ans,res); //取最小return res;}int sa(){random_shuffle(b.begin(), b.end()); //打乱，随机分布int n=a.size();for(double t=1e6;t>eps;t*=delta){int x=rand()%n,y=rand()%n;int last=fun(); //没有交换前的异或值之和swap(b[x],b[y]); //交换后的异或值之和int now=fun();int de=now-last;if(de<0){ //比当前优秀就要}else if(!(exp(-1.0*de/t)*RAND_MAX>rand()))  // 模拟退火的法则，我也搞不懂，背一下就好了swap(b[x],b[y]);  //不符合法则，回溯。}return ans;}int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {for(int i:nums1) a.push_back(i);for(int i:nums2) b.push_back(i);return sa();}
};