网站下拉菜单html做多大,wordpress 4.5 ueditor1.4.3.3,网络服务器配置与管理项目报告,网站搭建代理1、从计数到选择 ---- 递推与DP#xff08;动态规划#xff09; 2、从递归到记忆 ---- 子问题与去重复运算 3、动态规划的要点 第1题 网格路1(grid1) 小x住在左下角(0,0)处#xff0c;小y在右上角(n,n)处。小x需要通过一段网格路才能到小y家。每次#xff0c;小x可以选… 1、从计数到选择 ---- 递推与DP动态规划 2、从递归到记忆 ---- 子问题与去重复运算 3、动态规划的要点 第1题 网格路1(grid1) 小x住在左下角(0,0)处小y在右上角(n,n)处。小x需要通过一段网格路才能到小y家。每次小x可以选择下面任意一个方向前进 右方从(x,y)到点(x1,y) 上方从(x,y)到点(x,y1) 右上方从(x,y)到点(x1,y1)。
问小x有多少种走法到达小y家。 输入格式 一行一个整数n。1 ≤ n ≤ 500 输出格式 你的答案除以1 000 000 007的余数。 输入/输出例子1
输入
2 输出
13 样例解释
无 代码奉上
#includebits/stdc.h
using namespace std;
long long n;
long long f[505][505];
const long long mod1000000007;
int main(){scanf(%lld,n);n1; //题目中是00到nn我为了防止数组越界要1也会方便很多。f[0][0]1; //初始化。for(long long i1;in;i) for(long long j1;jn;j)f[i][j](f[i-1][j-1]%modf[i-1][j]%modf[i][j-1]%mod)%mod; //动态转移方程。printf(%d\n,f[n][n]%mod); return 0;
} 小问题推导大问题 ------ 子问题概念 测试2
第1题 好的序列(seq) 一个长为k的序列b1, b2, ..., bk (1 ≤ b1 ≤ b2 ≤ ... ≤ bk ≤ n)如果对所有的 i (1 ≤ i ≤ k - 1)满足bi | bi1那么它就是好的序列。这里a | b表示a是b的因子或者说a能整除b。
给出n和k求长度为k的好的序列有多少个。 输入格式 一行两个整数n,k。1 ≤ n,k ≤ 2000 输出格式 你的答案除以1 000 000 007的余数。 输入/输出例子1
输入
3 2 输出
5
样例说明
[1, 1], [2, 2], [3, 3], [1, 2], [1, 3]。 样例解释
无 代码奉上
#includecstdio
#includeiostream
#define rr register
using namespace std;
int cwh1000000007,n,k,f[2005][2005],ans;//用cwh表示1000000007更方便。
int main()
{scanf(%d%d,n,k);for(rr int i1;in;i)f[1][i]1;//赋值for(rr int i1;ik;i)//长度for(rr int jn;j0;j--)for(rr int k1;kn/j;k)//倍数f[i][j*k](f[i][j*k]f[i-1][j])%cwh;//方程for(rr int i1;in;i)ans(ansf[k][i])%cwh;//求答案printf(%d,ans);return 0;
}小问题推导大问题 两个方向改进后面从前面得到 测试3 第1题 卡牌游戏(card)
有三种卡牌记为A,B,C类型。每轮小x可以选择的出牌方法有 打出一张A牌 打出一张B牌 打出一张A牌和一张C牌 打出两张B牌和三张C牌。
问小x有多少种方法出完所有的牌。只要有一轮出牌的方法不一样就算作不同的方法。 输入格式 一行三个整数a,b,c依次表示卡牌A,B,C的数量。1 ≤ a,b,c ≤ 15 输出格式 你的答案除以1 000 000 007的余数。 输入/输出例子1
输入
2 2 3 输出
3 样例解释
无 代码奉上
#includebits/stdc.h
using namespace std;
int a,b,c;
int f[55][55][55];
const int mod1000000007;
int main(){cinabc;f[0][0][0]1; for(int i0;ia;i){for(int j0;jb;j){for(int k0;kc;k){ //枚举ABC卡牌的数量if(i1){f[i][j][k]f[i-1][j][k];f[i][j][k]%mod;} //DP记得特判不然会越界。下同。if(j1){f[i][j][k]f[i][j-1][k]%mod;f[i][j][k]%mod;}if(i1 k1){f[i][j][k]f[i-1][j][k-1]%mod;f[i][j][k]%mod;}if(j2 k3){f[i][j][k]f[i][j-2][k-3]%mod;f[i][j][k]%mod;}}}}coutf[a][b][c]%modendl;return 0;
}大问题分解为小问题 ------ 状态概念 小问题推导出大问题 ------- 计算方法方程 f[ a ][ b ][ c ]
测试4
第1题 四面体(tetra)
一只蚂蚁从点A出发每次行动可沿四面体的边来到另外一个点。问n次行动后蚂蚁回到点A有多少种方法。 输入格式 一行一个整数n。1 ≤ n ≤ 10^6 输出格式 你的答案除以1 000 000 007的余数。 输入/输出例子1
输入
2 输出
3 样例解释
无 代码奉上
#includebits/stdc.h
using namespace std;
long long n;
long long f[1000000][6];
const long long mod1000000007;
int main(){scanf(%lld,n);f[0][1]1;for(int i1;in;i){f[i][1](f[i-1][2]%modf[i-1][3]%modf[i-1][4]%mod)%mod;f[i][2](f[i-1][1]%modf[i-1][3]%modf[i-1][4]%mod)%mod;f[i][3](f[i-1][2]%modf[i-1][1]%modf[i-1][4]%mod)%mod;f[i][4](f[i-1][2]%modf[i-1][3]%modf[i-1][1]%mod)%mod;}printf(%d\n,f[n][1]);return 0;
}状态与阶段 测试5第1题 网格取数1
有N*M的方格每个方格里面有一个数字。你从左上角开始出发每次可以进入右边一个方格或下面一个方格不准出界。
问你选择怎样的线路到达右下角时线路上的数字和最大
例如下面是一个4*3的方格最优的路线如图所示 输入格式 第1行2个正整数N和M范围[2,100]。 下面N行每行M个整数每个整数范围[-100,100] 输出格式 一个整数。 输入/输出例子1 输入 3 3 1 2 3 4 5 6 9 9 9 输出 32 样例解释 无 代码奉上 #includebits/stdc.h
using namespace std;
long long n,m,a[1005][1005],b[1005][1005];
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(i1j1)b[i][j]a[i][j];else if(i1)b[i][j]b[i][j-1]a[i][j];else if(j1)b[i][j]b[i-1][j]a[i][j];else b[i][j](b[i-1][j]b[i][j-1])?b[i-1][j]a[i][j]:b[i][j-1]a[i][j];}}coutb[n][m];return 0;
} 总结
