如何将vs做的网站备份出来6,淘宝客返利网站建设,电商网站建设策划,wordpress会员查看发布插件文章目录 Bitset滚动数组多重背包区间DP树形dp状压dp模拟退火 Bitset
使用bitset需要引用bitset头文件。
其声明方法为:
std::bitsetNs; (N为s长度)常用函数#xff1a;
b.any() 判断b中是否存在值为1的二进制位
b.none() 判断b中是否不存在值为1的二… 文章目录 Bitset滚动数组多重背包区间DP树形dp状压dp模拟退火 Bitset
使用bitset需要引用bitset头文件。
其声明方法为:
std::bitsetNs; (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 i0;i5000;i){ansmin(dp[n1][iN],dp[n1][-iN]);if(ans1000) break;}
多重背包 //分堆过程while(ks){//小于等于和小于都可以,因为如果出现等于的情况就是s2^(k1)-1,下面的if判断会处理掉cnt;//cnt先下标从1开始w[cnt] k * wi;//k个物品为一堆v[cnt] k * vi;s-k;k*2;}if(s0){//如果存在最后一个堆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 i0;ig[u].size();i){int v g[u][i];if(vfa) continue;dfs(v,u);for(int km;k0;k--)for(int j1;jk;j)dp[u][k] max(dp[u][k],dp[u][k-j]dp[v][j]);}for(int im;i1;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][117];
int dfs(int x,int y){if(f[x][y])return f[x][y];int ans0;for(auto i:v[st[x][st[x].size()-1]])if(!((y(i-1))1))ansmax(ans,dfs(i,y|(1(i-1))));return f[x][y]ansst[x].size();
}for(int i1;in;i)cinst[i],v[st[i][0]].push_back(i);for(int i1;in;i)ansmax(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 eps1e-18;
const double delta0.999;//调了一年的参数一般为0.97~1.0class Solution {
public:vectorint a,b;int ansINT_MAX;//答案double fun(){int res0;for(int i0;ia.size();i)res(a[i]^b[i]);ansmin(ans,res); //取最小return res;}int sa(){random_shuffle(b.begin(), b.end()); //打乱随机分布int na.size();for(double t1e6;teps;t*delta){int xrand()%n,yrand()%n;int lastfun(); //没有交换前的异或值之和swap(b[x],b[y]); //交换后的异或值之和int nowfun();int denow-last;if(de0){ //比当前优秀就要}else if(!(exp(-1.0*de/t)*RAND_MAXrand())) // 模拟退火的法则我也搞不懂背一下就好了swap(b[x],b[y]); //不符合法则回溯。}return ans;}int minimumXORSum(vectorint nums1, vectorint nums2) {for(int i:nums1) a.push_back(i);for(int i:nums2) b.push_back(i);return sa();}
};
