CSDN博客

^-^,区间dp听的牛客的没听懂将就写着了后面还会出一个与区间dp相关的周报这里有点乱七八糟的。

。

。

.不过下面的背包问题和线性dp的知识点我觉得我记录的还可以嘻嘻╮(.

❛.)╭了解到一些知识点的名称——SG函数最小生成树KMP,KMP学了掌握进度百分之20吧。

晕晕的

o(ヘo#)

f[i][j]表示ai....aj的串中有多少个已经匹配的括号

f[i][j]max(f[i][j],f[i1][k-1]f[k1][j]2)——2是自己匹配的括号

[xxxxx]

strlen(a);memset(dp,0,sizeof(dp));for(int

len

ilen-1;if((a[i](a[j]))||(a[i][a[j]])){dp[i][j]

max(dp[i][j],dp[i1][j-1]2);}for(int

i;kj;k){dp[i][j]

max(dp[i][j],dp[i][k]dp[k1][j]);}

}printf(%d\n,dp[0][n-1]);}return

最长回文子序列

2.动态规划f[i][j]表示ai.....aj的串中最长回文子序列长度

如果ai与

的所有石子的得分·f[i,j]max(f[i][j],f[ik]f[k1][j]sum[i][j]-(sum[j]-sum[i-1]);sum[i][j]表示i到j的石子的价值和也可以前缀和实现sum【i】表示前i个石头的价值那么我们需要的就是sum[j]-sum[i-1]但是现在有环——可以通过取模的方法把他变成循环的也可以将序列加倍变成“1234

(nowcoder.com)

f[k][i][j];后k轮比赛中田忌使用了第i到第j匹马能够获得的最多的钱

k1;i1;jn;

dp[l][r-1]cost(r,k));}}coutdp[1][n];return

链接https://www.nowcoder.com/discuss/542652396985442304

来源牛客网

N个物品容量为V,每个物品有他的价值vi和权重wi每个物品只能用一次或0次

01背包问题每件物品只能最多用一次:

j0;jV;j){dp[i][j]dp[i-1][j];if(jv[i]){dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i]);}}}coutdp[N][V];return

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

为何能转化为1维

i-2及其之后的值。

于是可以在这次更新的时候将原来的更新掉反正以后也用不到。

所以对于

2.我们发现对于每次

或者j-v[i],不会用到之前后面的值所以为了防止串着改我们采取从后往前更新的方式用原来

;(如果从前往后更新的话前面的更新过之后会接着更新后面的值这样就不能保证是原来的

#includebits/stdc.h

jV;jv[i];j--){dp[j]max(dp[j],dp[j-v[i]]w[i]);}}coutdp[V];return

完全背包每件物品有无数个

k0;k*v[i]j;k){f[i][j]max(f[i-1][j],f[i-1][j-k*v[i]]k*w[i]);}}}coutf[N][V]endl;return

#includebits/stdc.h

j0;jV;j){f[i][j]f[i-1][j];if(j-v[i]0)f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);}}coutf[N][V]endl;return

#includebits/stdc.h

j0;jV;j){//if(j-v[i]0)f[i][j]max(f[i-1][j],f[i][j-v[i]]w[i]);else

f[i][j]f[i-1][j];}}coutf[N][V]endl;return

整理一下

k0;ks[i]k*v[i]j;k){f[i][j]max(f[i-1][j],f[i-1][j-v[i]*k]w[i]*k);}}}coutf[n][m];

多重背包不能用完全背包的优化方式因为完全背包个数是无数个多重背包个数是有限个没所以写式子的时候就是

已知第二段式子的最大值并不能求出第二段除红色框以外的最大值所以这种方法不可取

知道两个绿色的最大值并不能知道粉色线的最大值。

所以就不能直接用完全背包的方式优化

用二进制方式优化

如果仍然不是很能理解的话取这样一个例子:要求在一堆苹果选出n个苹果。

我们传统的思维是一个一个地去选选够n个苹果就停止。

这样选择的次数就是n次

二进制优化思维就是现在给出一堆苹果和10个箱子选出n个苹果。

将这一堆苹果分别按照1,2,4,8,16,.....512

124816512

(第11个箱子才能取到1024)都可以从这10个箱子里的苹果数量表示出来但是这样选择的次数就是

#includebits/stdc.h

a,b,s;cinabs;//a是第i种物品的体积b是第i种物品的价值//s是第i种物品的数量int

k1;while(ks){//进行二进制分组cnt;v[cnt]a*k;//第cnt组的体积就是一个物品的体积乘以cnt组的数量w[cnt]b*k;//价值同理s-k;//将s拆分k*2;}if(s0){//算C;cnt;v[cnt]a*s;w[cnt]b*s;}}ncnt;for(int

i1;in;i){//01背包问题怎么从这n种中选择最大的价值//这n种可以组成0-s的数字其中一个for(int

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

}coutf[m]endl;return

j0;js[i];j){cinv[i][j]w[i][j];}}for(int

i1;in;i){for(int

k0;ks[i];k){if(v[i][k]j){f[j]max(f[j],f[j-v[i][k]]w[i][k]);}

0;}

j0;ji1;j){//这里要多初始化一点w[i][j]-1e9;}}w[1][1]a[1][1];for(int

i2;in;i){for(int

j1;ji;j){w[i][j]max(w[i-1][j-1]a[i][j],w[i-1][j]a[i][j]);}}int

res-1e9;for(int

i1;in;i){resmax(res,w[n][i]);}coutresendl;return

0;}

最长上升子序列的长度等于f[j]1(1是后面以i结尾的那个数);

a[i]max(a[j]1);ajai

i1;in;i){f[i]1;//只有a[i]一个数的情况for(int

j1;ji;j){if(a[i]a[j]){f[i]max(f[i],f[j]1);}}}int

res0;for(int

i1;in;i){resmax(res,f[i]);}coutresendl;return

怎么记录最长子序列有那些数

i1;in;i){f[i]1;//只有a[i]一个数的情况g[i]0;for(int

j1;ji;j){if(a[i]a[j]){if(f[i]f[j]1){f[i]f[j]1;g[i]j;//记录转移}}}}int

k1;for(int

i1;in;i){if(f[k]f[i]){ki;}}coutf[k]endl;for(int

i0,lenf[k];ilen;i){couta[k];kg[k];//这里是倒着输出的}return

最长公共子序列

main(){cinnm;scanf(%s%s,a1,b1);for(int

i1;in;i){for(int

j1;jm;j){f[i][j]max(f[i-1][j],f[i][j-1]);if(a[i]b[j]){f[i][j]max(f[i][j],f[i-1][j-1]1);}}}coutf[n][m]endl;return

这周增添的讲题环节虽然说能多多少少听懂一些学姐学长的思路但是毕竟知识点跨度较大我觉地emmmm......可能对我帮助没有那么大再者就是讲题的时候有些同学更注重讲解如何去做题其实题意讲述明白也是很重要的哇T-T。

有些东西光听是记不住的过几天也就忘了但是星期五晚上的牛客讲题是好的毕竟题目都看过了也有所思考以我们目前的水平补充点知识是能做的就是看不懂题解学长讲了题目的算法有哪些可以私下再去填充然后上手补题我觉地这是很好的至于星期六晚上的那堂课呜呜呜算法小白有种高一生听高考题的感觉其实我就觉的我们目前还是得把基础打牢一点吧先不要去试图建立高楼有些东西听了也就只是听过要实实在在的得到东西还是得通过练习听后有练习才是听课的价值所在。

T-T

over: