[GN] DP学习笔记板子

本文介绍: 使用bitset需要引用。

文章目录

- Bitset
- 滚动数组
- 多重背包
- 区间DP
- 树形dp
- 状压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.0

class 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();
    }
};