自适应型网站建设多少钱,广州棠下网站建设,莱芜网站优化是什么,免费咨询标志前言
这是一道比较久之前的题了#xff0c;之前没做完。不过这次不是因为我改了#xff0c;而是数据改了#xff08;可能之前有问题#xff09;#xff0c;然后偶然今天翻的时候就发现自己对了QAQ。 题目
OJ1306 就是给出两个序列#xff0c;求出这两个序列中公共的最…前言
这是一道比较久之前的题了之前没做完。不过这次不是因为我改了而是数据改了可能之前有问题然后偶然今天翻的时候就发现自己对了QAQ。 题目
OJ1306 就是给出两个序列求出这两个序列中公共的最长的子上升序列。 解题思路
这里用的是比较慢的方法。就是4重循环。 代码
#includecstdio
#includeiostream
#includecstring
using namespace std;
int b[501][501],b2[501][501],f[501][501],a1[501],a2[501],max1,max2,m1,m2;
bool ok[501][501];
void print(int x,int y)
{if (b[x][y]0 b2[x][y]0 || x0 || y0) {printf(%d ,a1[x]);return;}print(x-b[x][y],y-b2[x][y]);printf(%d ,a1[x]);
}//输出序列
int main()
{scanf(%d,m1);for (int i1;im1;i) scanf(%d,a1[i]);scanf(%d,m2);for (int i1;im2;i) scanf(%d,a2[i]); //输入for (int i1;im1;i)//枚举第一个序列开头{for (int j1;jm2;j)//枚举第二个开头{f[i][j]1;//改变if (f[i][j]f[i-1][j]){f[i][j]f[i-1][j];b[i][j]1;b2[i][j]0;}//判断路径输出if (f[i][j]f[i][j-1]){f[i][j]f[i][j1];b[i][j]0;b2[i][j]1;}//判断路径输出if (a1[i]a2[j])//开头相同{for (int k1;ki;k)for (int k21;k2j;k2)//往下枚举{if (f[i][j]f[i-k][j-k2]1 a1[i]a1[i-k] a1[i-k]a2[j-k2]){f[i][j]f[i-k][j-k2]1;//动态转移b[i][j]k;b2[i][j]k2;//记录过程}}if (f[max1][max2]f[i][j]) {max1i;max2j;}//改变最大值}else {ok[i][j]true;}//输出防止输出没有的数}}printf(%d\n,f[max1][max2]);if (f[max1][max2]!0){print(max1,max2);}
}
