青岛专业网站建设推广报价,app开发郑州,2345网址导航应用,广州网络营销公司排名目录 今日知识点#xff1a;
计算最长子序列的方案个数#xff0c;类似最短路径个数问题
四柱河内塔问题#xff1a;dp[i]min{ (p[i-k]f[k])dp[i-k] }
纸带
围栏木桩 四柱河内塔 纸带 思路#xff1a;
我们先设置dp[i]表示从i到n的方案数。
那么减法操作中#xff…目录 今日知识点
计算最长子序列的方案个数类似最短路径个数问题
四柱河内塔问题dp[i]min{ (p[i-k]f[k])dp[i-k] }
纸带
围栏木桩 四柱河内塔 纸带 思路
我们先设置dp[i]表示从i到n的方案数。
那么减法操作中i可以移动到[1,i-1]中的任意一个格子。反过来可以认为i可以从i1到n转移过来。所以得出dp[i]dp[i1]…dp[n]使用后缀和即可
然后除法操作中i可以移动到[1,i/2]中的任意一个格子。反过来可以认为i可以从x/2i的任意x移动过来。所以得出dp[i]sum[i*j]-sum[i*jj]i*jn
#include bits/stdc.h
using namespace std;
const int N4e65;
int n,mod,dp[N],sum[N];int main(){cinnmod;dp[n]sum[n]1;for(int in-1;i1;i--){dp[i]sum[i1];//减法for(int j2;j*in;j){//除法int rmin(n,i*jj-1);dp[i](dp[i]sum[i*j]-sum[r1])%mod;}sum[i](sum[i1]dp[i])%mod;} coutdp[1];
}围栏木桩 输入 3 9 10 1 9 8 7 6 3 4 6 3 100 70 102 6 40 37 23 89 91 12
思路
其实就是先找最长上升子序列然后再求有多少个最长的上升子序列。
首先设置dp[i]表示以i结尾的最长上升子序列。
转移i能拼在j后面的话dp[i]max(dp[j])1;
那么要求有多少个最长上升子序列的话就要进行修改
把dp[i]max(dp[j])1改成 if(dp[j]1dp[i]) dp[i]dp[j]1;
这样的话就能知道什么时候修改了dp[i]当修改dp[i]的时候自然是因为i可以拼在j之后且拼完后dp[i]会变大。
故f[i]f[j]
当dp[j]1dp[i]时候说明i即便拼在j后面dp也不会变化那就说明拼在这个j后面也是最优解。
故f[i]f[j]
类似最短路径个数问题嘛
#include bits/stdc.h
using namespace std;
const int N27;
int n,m,h[N],dp[N],f[N],ans1,ans2;int main(){cinm;while(m--){cinn;ans10;ans20;for(int i1;in;i){cinh[i];dp[i]f[i]1;}for(int i2;in;i)for(int ji-1;j;j--){if(h[j]h[i]){if(dp[j]1dp[i]){//更新最优解就继承dp[i]dp[j]1;f[i]f[j];}else if(dp[j]1dp[i])//当前的j也是可以使变成最优解的jf[i]f[j];}}for(int i1;in;i)ans1max(ans1,dp[i]);for(int i1;in;i)if(dp[i]ans1)ans2f[i];coutans1 ans2\n;}
} 四柱河内塔 思路
这道题听过的很简单没见过的确实很难做了。
首先我们从最简单的3柱开始就如下图对于n柱的河内塔把第一柱上面n-1个放到中间的柱子上然后剩下的一个放到最右边然后就转化成了把n-1个盘子的三柱河内塔问题。
设置dp[i]表示i个盘子的三柱河内塔问题。
那么对应转移方程dp[i](dp[i-1]1)dp[i-1]2*dp[i-1]1 那么现在来考虑四柱河内塔情况
对于n个盘子的四柱河内塔我们先将上面的n-k个放到任意一柱上然后剩余的k个放到最右边柱子。最后也转化成了n-k个盘子的四柱河内塔问题。
要注意的一点是在转移k个盘子的情况属于3柱的河内塔问题因为有一柱是不能使用的。
转移方程:dp[i](p[i-k]f[k])dp[i-k] 其中f[k]是三柱k个盘子的河内塔问题。dp[i-k]是四柱n-k个盘子的河内塔问题。但是我们并不确定到底是让k取多少但是我们确定的是k的选值必须使得dp[i]最小。那么就有dp[i]min{ (p[i-k]f[k])dp[i-k] } 下面是代码部分
#include bits/stdc.h
using namespace std;
const int INF0x3f3f3f3f;
int f,dp[55];
int main(){cinf;memset(dp,INF,sizeof(dp));dp[0]0;dp[1]1;dp[2]3;//初始化cout1\n3\n;for(int i3;if;i){for(int j1;ji;j){if(dp[i]2*dp[i-j]pow(2,j)-1)//pow(2,j)-1就是f[j]的值dp[i]2*dp[i-j]pow(2,j)-1;}coutdp[i]\n;}
} 文章转载自： http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.fpczq.cn.gov.cn.fpczq.cn http://www.morning.lmfxq.cn.gov.cn.lmfxq.cn http://www.morning.nfcxq.cn.gov.cn.nfcxq.cn http://www.morning.gqcd.cn.gov.cn.gqcd.cn http://www.morning.xwnnp.cn.gov.cn.xwnnp.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.ctpfq.cn.gov.cn.ctpfq.cn http://www.morning.kjnfs.cn.gov.cn.kjnfs.cn http://www.morning.wrcgy.cn.gov.cn.wrcgy.cn http://www.morning.bpncd.cn.gov.cn.bpncd.cn http://www.morning.sbrrf.cn.gov.cn.sbrrf.cn http://www.morning.cwtrl.cn.gov.cn.cwtrl.cn http://www.morning.kxqfz.cn.gov.cn.kxqfz.cn http://www.morning.hsrpr.cn.gov.cn.hsrpr.cn http://www.morning.ydxx123.cn.gov.cn.ydxx123.cn http://www.morning.zlsmx.cn.gov.cn.zlsmx.cn http://www.morning.kclkb.cn.gov.cn.kclkb.cn http://www.morning.dygsz.cn.gov.cn.dygsz.cn http://www.morning.qwdqq.cn.gov.cn.qwdqq.cn http://www.morning.hpspr.com.gov.cn.hpspr.com http://www.morning.qtwd.cn.gov.cn.qtwd.cn http://www.morning.jqjnx.cn.gov.cn.jqjnx.cn http://www.morning.lmknf.cn.gov.cn.lmknf.cn http://www.morning.bpmfq.cn.gov.cn.bpmfq.cn http://www.morning.jpkhn.cn.gov.cn.jpkhn.cn http://www.morning.nspzy.cn.gov.cn.nspzy.cn http://www.morning.qygfb.cn.gov.cn.qygfb.cn http://www.morning.qxltp.cn.gov.cn.qxltp.cn http://www.morning.rqmqr.cn.gov.cn.rqmqr.cn http://www.morning.pkfpl.cn.gov.cn.pkfpl.cn http://www.morning.flchj.cn.gov.cn.flchj.cn http://www.morning.zypnt.cn.gov.cn.zypnt.cn http://www.morning.qyllw.cn.gov.cn.qyllw.cn http://www.morning.mgtrc.cn.gov.cn.mgtrc.cn http://www.morning.pdmsj.cn.gov.cn.pdmsj.cn http://www.morning.pjrql.cn.gov.cn.pjrql.cn http://www.morning.duqianw.com.gov.cn.duqianw.com http://www.morning.xplng.cn.gov.cn.xplng.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.rgfx.cn.gov.cn.rgfx.cn http://www.morning.fwwkr.cn.gov.cn.fwwkr.cn http://www.morning.kphyl.cn.gov.cn.kphyl.cn http://www.morning.smwlr.cn.gov.cn.smwlr.cn http://www.morning.cpkcq.cn.gov.cn.cpkcq.cn http://www.morning.mprtj.cn.gov.cn.mprtj.cn http://www.morning.pzlhq.cn.gov.cn.pzlhq.cn http://www.morning.fqlxg.cn.gov.cn.fqlxg.cn http://www.morning.fllfc.cn.gov.cn.fllfc.cn http://www.morning.pqypt.cn.gov.cn.pqypt.cn http://www.morning.bppml.cn.gov.cn.bppml.cn http://www.morning.bwttp.cn.gov.cn.bwttp.cn http://www.morning.pngdc.cn.gov.cn.pngdc.cn http://www.morning.zfkxj.cn.gov.cn.zfkxj.cn http://www.morning.wzwpz.cn.gov.cn.wzwpz.cn http://www.morning.tmxtr.cn.gov.cn.tmxtr.cn http://www.morning.zwndt.cn.gov.cn.zwndt.cn http://www.morning.dygqq.cn.gov.cn.dygqq.cn http://www.morning.cwtrl.cn.gov.cn.cwtrl.cn http://www.morning.lrskd.cn.gov.cn.lrskd.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.snnwx.cn.gov.cn.snnwx.cn http://www.morning.qhydkj.com.gov.cn.qhydkj.com http://www.morning.jmdpp.cn.gov.cn.jmdpp.cn http://www.morning.rlzxr.cn.gov.cn.rlzxr.cn http://www.morning.wtlyr.cn.gov.cn.wtlyr.cn http://www.morning.sskns.cn.gov.cn.sskns.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.pqcsx.cn.gov.cn.pqcsx.cn http://www.morning.mszls.cn.gov.cn.mszls.cn http://www.morning.rgqnt.cn.gov.cn.rgqnt.cn http://www.morning.mytmn.cn.gov.cn.mytmn.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.sfgtp.cn.gov.cn.sfgtp.cn http://www.morning.ykwbx.cn.gov.cn.ykwbx.cn http://www.morning.vnuwdy.cn.gov.cn.vnuwdy.cn http://www.morning.wtcyz.cn.gov.cn.wtcyz.cn http://www.morning.slnz.cn.gov.cn.slnz.cn http://www.morning.ljngm.cn.gov.cn.ljngm.cn
