网站制作建设兴田德,拼多多网上购物商城,手机网站制作多少钱,北京品牌网站建设公司哪家好目录 今日知识点#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;}
}
