织梦网站怎么居中,企业安全文化建设导则,网页浏览器tv版,多用户分布式网站开发目录 1、乌龟棋 2、最长上升子序列 3、最长公共子序列 4、松散子序列 5、最大上升子序列和 1、乌龟棋
小明过生日的时候#xff0c;爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘只有一行#xff0c;该行有 N 个格子#xff0c;每个格子上一个分数#xff08;非负整数爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘只有一行该行有 N 个格子每个格子上一个分数非负整数。
棋盘第 1 格是唯一的起点第 N 格是终点游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中共有 M 张爬行卡片分成 4 种不同的类型M 张卡片中不一定包含所有 4 种类型的卡片每种类型的卡片上分别标有 1、2、3、4 四个数字之一表示使用这种卡片后乌龟棋子将向前爬行相应的格子数。
游戏中玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片控制乌龟棋子前进相应的格子数每张卡片只能使用一次。
游戏中乌龟棋子自动获得起点格子的分数并且在后续的爬行中每到达一个格子就得到该格子相应的分数。
玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显用不同的爬行卡片使用顺序会使得最终游戏的得分不同小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在告诉你棋盘上每个格子的分数和所有的爬行卡片你能告诉小明他最多能得到多少分吗
输入格式
输入文件的每行中两个数之间用一个空格隔开。
第 1 行 2 个正整数 N 和 M分别表示棋盘格子数和爬行卡片数。
第 2 行 N 个非负整数a1,a2,……,aN其中 ai表示棋盘第 i 个格子上的分数。
第 3 行 M 个整数b1,b2,……,bM表示 M 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 M 张爬行卡片。
输出格式
输出只有 1 行包含 1 个整数表示小明最多能得到的分数。
数据范围
1≤N≤350 1≤M≤120 0≤ai≤100 1≤bi≤4 每种爬行卡片的张数不会超过 40。
输入样例
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1输出样例
73
思路
用四个维度表示四个卡片的消耗量状态转移方程
auto vf[b1][b2][b3][b4];可以减少代码量 int ta[b12*b23*b34*b41];auto vf[b1][b2][b3][b4];if(b1)vmax(v,f[b1-1][b2][b3][b4]t);if(b2)vmax(v,f[b1][b2-1][b3][b4]t);if(b3)vmax(v,f[b1][b2][b3-1][b4]t);if(b4)vmax(v,f[b1][b2][b3][b4-1]t); 代码
#includebits/stdc.husing namespace std;const int N41;int a[360];int b[5];int n,m;int f[N][N][N][N];int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,a[i]);for(int i1;im;i){int t;scanf(%d,t);b[t];//coutb[t];}for(int b10;b1b[1];b1)for(int b20;b2b[2];b2)for(int b30;b3b[3];b3)for(int b40;b4b[4];b4){f[b1][b2][b3][b4]a[b12*b23*b34*b41];}for(int b10;b1b[1];b1)for(int b20;b2b[2];b2)for(int b30;b3b[3];b3)for(int b40;b4b[4];b4){int ta[b12*b23*b34*b41];auto vf[b1][b2][b3][b4];if(b1)vmax(v,f[b1-1][b2][b3][b4]t);if(b2)vmax(v,f[b1][b2-1][b3][b4]t);if(b3)vmax(v,f[b1][b2][b3-1][b4]t);if(b4)vmax(v,f[b1][b2][b3][b4-1]t);}coutf[b[1]][b[2]][b[3]][b[4]];return 0;
}
2、最长上升子序列
给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N个整数表示完整序列。
输出格式
输出一个整数表示最大长度。
数据范围
1≤N≤1000 −1e9≤数列中的数≤109
输入样例
7
3 1 2 1 8 5 6输出样例
4
思路
状态转移方程 if(a[j]a[i])f[i]max(f[i],f[j]1);resmax(res,f[i]); 代码
#includebits/stdc.husing namespace std;const int N1003;int a[N];int n;int f[N];//以i结尾的最长子序列数 int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),f[i]1;int res-1;for(int i1;in;i)for(int j0;ji;j){if(a[j]a[i])f[i]max(f[i],f[j]1);resmax(res,f[i]);} coutres;return 0;
}
3、最长公共子序列
给定两个长度分别为 N和 M 的字符串 A 和 B求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串表示字符串 A。
第三行包含一个长度为 M 的字符串表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数表示最大长度。
数据范围
1≤N,M≤1000
输入样例
4 5
acbd
abedc输出样例
3
思路
状态转移方程 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);resmax(res,f[i][j]); 代码
#includebits/stdc.husing namespace std;int n,m;const int N1003;char a[N],b[N];int f[N][N]; int main()
{cinnm;int res-1;for(int i1;in;i)cina[i];for(int i1;im;i)cinb[i];//for(int i1;im;i)coutb[i];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);resmax(res,f[i][j]);}coutres;return 0;
}
4、松散子序列
给定一个仅含小写字母的字符串 s假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi 个字符。
我们定义 s 的一个松散子序列为对于 i1 总是有 pi − pi−1≥2。
设一个子序列的价值为其包含的每个字符的价值之和a∼z 分别为 1∼26。
求 s 的松散子序列中的最大价值。
输入格式
输入一行包含一个字符串 s。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 20% 的评测用例|s|≤10 对于 40% 的评测用例|s|≤300 对于 70% 的评测用例|s|≤5000 对于所有评测用例1≤|s|≤1e6字符串中仅包含小写字母。
输入样例
azaazaz输出样例
78
思路
状态转移方程 f[i]max(f[i],f[i-1]);if(i-20)f[i]max(f[i],f[i-2](a[i]-a1)); 代码
#includebits/stdc.husing namespace std;const int N1e610;char a[N];int f[N];int main()
{scanf(%s,a1);//从1索引开始读取int nstrlen(a1);for(int i1;in;i){//couta[i] ;f[i]a[i]-a1;}//int res-1;for(int i1;in;i){f[i]max(f[i],f[i-1]);if(i-20)f[i]max(f[i],f[i-2](a[i]-a1));//coutf[i]endl;//resmax(res,f[i]);还可以再优化} coutf[n];return 0;
}
5、最大上升子序列和
一个数的序列 bi当 b1b2…bS 的时候我们称这个序列是上升的。
对于给定的一个序列(a1,a2,…,aN)我们可以得到一些上升的子序列(ai1,ai2,…,aiK)这里1≤i1i2…iK≤N。
比如对于序列(1,7,3,5,9,4,8)有它的一些上升子序列如(1,7),(3,4,8)等等。
这些子序列中和最大为18为子序列(1,3,5,9)的和。
你的任务就是对于给定的序列求出最大上升子序列和。
注意最长的上升子序列的和不一定是最大的比如序列(100,1,2,3)的最大上升子序列和为100而最长上升子序列为(1,2,3)。
输入格式
输入的第一行是序列的长度N。
第二行给出序列中的N个整数这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数表示最大上升子序列和。
数据范围
1≤N≤1000
输入样例
7
1 7 3 5 9 4 8输出样例
18
思路
状态转移方程 if(a[i]a[j])f[i]max(f[i],f[j]a[i]); 代码
#includebits/stdc.husing namespace std;const int N1003;int a[N];int f[N]; int main()
{int n;cinn;for(int i1;in;i){cina[i];f[i]a[i];}int res-1;for(int i1;in;i)for(int j0;ji;j){//f[i]max(f[i],f[j]);错误的虽然j比i小a[j]不一定比a[i]小if(a[i]a[j])f[i]max(f[i],f[j]a[i]);//coutf[i] ;resmax(res,f[i]);}coutres;return 0;
}
