0-1背包多重背包多重背包问题

石子合并锯木棍并查集Dijkstra单源最短路Python进制转换(整数无限大)全排列神奇的口袋全排列II放苹果求第k小八皇后问题哈夫曼编码KMP算法遍历建立二叉树

头文件与STL

std;vector.insert(vector.begin(),2,99)//在头部插入2个99

vector.end())

priority_queueint,vecotrint,greaterint;

python输入

需要额外的ans存储max因为是子串dp[i1]max(dp[i]a[i],a[i]);ansmax(dp[i1],ans);

}最长公共子序列

j1;js2.size();j){if(s1[i-1]s2[j-1])dp[i][j]dp[i-1][j-1]1;else

dp[i][j]max(dp[i-1][j],dp[i][j-1]);}

}最长连续公共子串

j1;jm;j){if(s1[i-1]s2[j-1]){dp[i][j]dp[i-1][j-1]1;//

号确保

如果不唯一则输出s1中的最后一个。

if(dp[i][j]maxLen){maxLendp[i][j];//存储公共子串在s1中的末尾位置可以输出子串ti-1;}}

}最长递增子序列

https://www.nowcoder.com/practice/cf209ca9ac994015b8caf5bf2cae5c98?tpId40tagstitledifficulty0judgeStatus0rp1sourceUrl

for(int

j0;ji;j){//dp[i]代表以i结尾的最长递增子序列数if(a[i]a[j])dp[i]max(dp[j]1,dp[i]);ansmax(dp[i],ans);}

}最大上升子序列和

和上述最长递增子序列思路一致不过dp[i]代表以i结尾的最长递增子序列的和用ans存储结果

0-1背包

dp[1001][1001];//代表前i个物体背包为j的最大价值

int

j1;jbag;j){if(jv[i]){dp[i][j]max(dp[i-1][j-v[i]]w[i],dp[i-1][j]);}else{dp[i][j]dp[i-1][j];}}

coutdp[n][bag];多重背包

jv[i];jm;j){dp[j]max(dp[j],dp[j-v[i]]w[i]);}

}多重背包问题

dp[i](dp[i-1]dp[i/2])%1000000000;最小邮票

dp[0][0]0;

j1;jm;j){if(j-a[i]0)dp[i][j]min(dp[i-1][j-a[i]]1,dp[i-1][j]);elsedp[i][j]dp[i-1][j];}

}最大子矩阵

dp[k-1][q-1]);x1k;x2i;y1q;y2j;}}}}}cout

ansendl;coutx1y1

求n以内的所有素数时间O(nlog(logn))【不是最优例如14会被2和7筛重复2次】

void

continue;//i是素数添加进数组,并筛掉与i成倍数的非素数else

{primes[cnt

j2*i;jn;ji){//j一定不是素数st[j]true;}}}

}线性筛素数

j0;jprime_count;j){if(prime[j]*in)

break;//翻倍一个数

st[primes[j]*i]true;//退出循环避免之后重复进行筛选if(i%primes[j]0)

break;}

x;cinx;ve.push_back(x);if(min_sumve[i]ve[i-1]){min_sumve[i]ve[i-1];min_idxi;}}while(ve.size()2){ans

min_sum;ve[min_idx]ve[min_idx]ve[min_idx-1];ve.erase(ve.begin()min_idx-1);min_sum1e7;

break;

i1;ive.size();i){if(min_sumve[i]ve[i-1]){min_sumve[i]ve[i-1];min_idxi;}}}coutansendl;

锯木棍

{//priority_queueint,vectorint,greaterint

que;priority_queueint,vectorint,cmp

que;int

ans0;while(n--){cintmp;que.push(tmp);}

bque.top();que.pop();que.push(ab);ansansab;}coutans;

return

b){root1Find(a);root2Find(b);if(root2root1)return

;else{s[root2]root1;}}Dijkstra单源最短路

int

line.split()aint(a[0])bbin(a)s(b[2:][::-1])print(int(s,2))

全排列

i1;in;i){//还没访问的数if(!st[i]){st[i]true;//

恢复-现场st[i]false;}}

有一个神奇的口袋总容积是40有n个物品,体积为Vi装满40有多少种装法

void

}else{//从j开始前面用过的舍弃掉防止重复for(int

ij;in;i){if(!st[i]){st[i]true;dfs(uv[i],i);st[i]false;}}}

}全排列II

i1;in;i){//还没访问的数if(!st[i]){st[i]true;//

恢复-现场st[i]false;//***当与后一个元素重复时跳过不排列,且这一步要在恢复现场之后做while(s[i1]s[i])i;}}

int

cinn;//使重复的元素排在一起sort(a,an);dfs(1);}放苹果

把M个同样的苹果放在N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法

//处理边界

i0;im;i){//为0的可以不用处理数组默认为0//1个盘子的dp[i][1]1;

for(int

j1;jn;j){//如果盘子多多余的用不到的盘子都是没用的if(ji){dp[i][j]dp[i][i];}//如果苹果多dp[i][j]等于

有空盘子的(挑一个盘子为空)没有空盘子(每个盘子初始都放一个苹果)的状态else{dp[i][j]dp[i][j-1]dp[i-j][j];}}

}求第k小

{r--;}swap(a[l],a[r]);}a[l]pivot;if(lk-1)

{couta[l];return

if(lk){partition(l1,end);}else{partiton(start,l);}

}int

{cina[i];}partition(0,n-1);return

}八皇后问题

priority_queueint,vectorint,greaterint

int

pattern[j]pattern[i]){i;j;next[j]i;}else{inext[i];}}return

}int

s[i]pattern[j]){i;j;}else{jnext[j];}}if(jm){return

-1;}

c):data©,left(nullptr),right(nullptr){};

using

c):data(c),left(nullptr),right(nullptr){};

};TreeNode*

style(TreeNode*)malloc(sizeof(TreeNode))rootnew

TNode(c);char

c1s[cnt];root-leftBuild(root-left,c1);char

c2s[cnt];root-rightBuild(root-right,c2);return

root;

root){if(root-left)Inorder(root-left);coutroot-dataendl;if(root-right)Inorder(root-right);}

void

TNULL;TBuild(T,s[cnt]);Inorder(T);return