JSOI夏令营普及2C例题及上机题解.doc

20170704-11JSOI夏令营普及2C例题及上机题解7.5 穷举与应用1.方格填数【by 】问题描述输入格式输出格式输入样例#1输出样例#1输入样例#2输出样例#2解题思路参考代码2.火柴棒不等式【by 】问题描述输入格式输出格式输入样例#1输出样例#1输入样例#2输出样例#2解题思路参考代码3.除法【by 】问题描述输入格式输出格式输入样例#1输出样例#1输入样例#2输出样例#2解题思路参考代码7.6 算法评价及举例，基于贪心的算法及应用举例1.H数问题【by 】试题原型：P2723 丑数 Humble Numbers(/problem/show?pid=2723)问题描述所谓H数，是指只含有2,3,5,7这些质因数的数，如630是H数，而22不是。现在要求输出第n个H数，为了方便起见将H1定为1。已知n不超过10000，最后数据在long long范围之内。输入格式一个数n(如题目)输出格式第n个H数输入样例#130输出样例#149输入样例#21输出样例#21解题思路队列模拟生成，类似bash数集，合并果子，蚯蚓参考代码#includeusing namespace std;const int maxn=10000+50;long long amaxn;int main() int n,i,t2,t3,t5,t7,tail;long long tmp; cinn;a1=1;t2=t3=t5=t7=1;tail=2;for(i=2;i=n;i+)tmp=min(at2*2,min(at3*3,min(at5*5,at7*7);atail+=tmp;if(tmp=at2*2)t2+;if(tmp=at3*3)t3+;if(tmp=at5*5)t5+;if(tmp=at7*7)t7+;coutanendl;2.删数问题【by 】/problem/show?pid=1106问题描述 键盘输入一个高精度的正整数N，去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和k，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新的正整数。（N不超过250位） 输入数据均不需判错。输入格式n (高精度的正整数)k (需要删除的数字个数)输出格式最后剩下的最小数。输入样例#1175438 4 输出样例#113解题思路贪心，分k轮，若整体为升序，删去升序的最后一个，其余删去开始降序的第一个。细节处理：1.输出需去除新数多余的前导0，并至少输出最后一位；参考代码#includeusing namespace std;const int maxn=250+50;char amaxn;int main()int k,i,j,pos,len,flag=0;scanf(%s%d,a,&k);len=strlen(a);for(i=1;i=k;i+)pos=len-1;for(j=0;jaj+1)pos=j;break;for(j=pos;jlen-1;j+)/整体前移 aj=aj+1;alen-1=0;len-;/长度减1 pos=len-1;for(i=0;ilen;i+)/找到第一个非0字符，保留1位 if(ai!=0)pos=i;break;for(i=pos;ilen;i+)printf(%c,ai);printf(n);3.三国游戏【by 】来源：/problem/show?pid=1199问题描述小涵很喜欢电脑游戏，这些天他正在玩一个叫做三国的游戏。在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有 N 位武将（N为偶数且不小于 4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵计算机小涵”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。 下面举例说明计算机的选将策略，例如，游戏中一共有 6 个武将，他们相互之间的默契值如下表所示：双方选将过程如下所示：小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？ 假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。输入格式共 N 行。第一行为一个偶数 N，表示武将的个数。第 2 行到第 N 行里，第（i+1）行有（Ni）个非负整数，每两个数之间用一个空格隔开，表示 i 号武将和 i+1，i+2，N 号武将之间的默契值（0默契值1,000,000,000）。输出格式共 1 或 2 行。若对于给定的游戏输入，存在可以让小涵获胜的选将顺序，则输出 1，并另起一行输出所有获胜的情况中，小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序，则输出 0。输入样例#16 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12输出样例#1132输入样例#28 42 24 10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 输出样例#2177数据范围对于 40%的数据有 N10。对于 70%的数据有 N18。对于 100%的数据有 N500解题思路贪心，先选择表中次大武将默契值中的一个武将，则计算机必定选择最优解，则可成功选择次优解，同时，由于最优解的一方武将计算机无法选到，故各行次优解的最大值即为最终最大默契值。参考代码#includeusing namespace std;const int maxn=500+20;int amaxnmaxn,m1maxn,m2maxn;int n;int main()int i,j,ans=0;scanf(%d,&n);for(i=1;in;i+)for(j=i+1;j=n;j+)scanf(%d,&aij);aji=aij;for(i=1;i=n;i+)for(j=1;j=m1i)/若大于等于最大值，更新最大值、次优值 m2i=m1i;m1i=aij;else if(aijm2i) m2i=aij;/若大于次大值，更新次优值 ans=max(ans,m2i);/更新次优值中的最大值 printf(1n%dn,ans);return 0;7.7 递推与递归，分治（二分、快排）1.合理排列【by 】问题描述由m个A，n个B组成若干个排列。从某个排列的位置1开始数，数到任意位置时都能保证A的个数不少于B的个数，则称该排列为合理排列。例如：当m=2，n=2时排列有 A A B B(合理) A B A B(合理)A B B A(不合理) B B A A(不合理)合理排列数有2种输入格式只有一行两个整数m,n（1nm12）（用空格分隔）输出格式一个整数（所有的合理排列数）输入样例#13 2 输出样例#15解题思路参考代码#includeusing namespace std;int n,m,cnt=0;void dfs(int i,int j)if(i=m&j=n)cnt+;return;if(im)dfs(i+1,j);if(jn&ji)dfs(i,j+1);int main()int i,j,ans=0;scanf(%d%d,&m,&n);dfs(0,0);printf(%dn,cnt);return 0;2.网线主管【by 】来源：/problem/show?pid=1297问题描述Wonderland居民决定举行一届地区性程序设计大赛。仲裁委员会志愿负责这次赛事并且保证会组织一次有史以来最公正的比赛。为此，所有参赛者的电脑和网络中心会以星状网络连接，也就是说，对每个参赛者，组委会会用一根长度一定的网线将他的计算机与中心连接，使得他们到网络中心的距离相等。为了买网线，组委会与当地的网络公司联系，要向他们购买一定数目的等长网线，这些网线要尽可能的长，使得组织者可以让选手们彼此远离。于是公司指派管理网线事务的负责人解决此事。负责人清楚地知道仓库里每根网线的长度(精确到厘米：cm)，他也可以将他们以厘米的精度切割前提是他得知道切成多长。但是现在，这个长度他算不出来，于是他彻底迷茫了。你要做的，就是帮助困惑的负责人。编一个程序求出为了得到一定数目的等长网线，每根网线最大的可能长度。输入格式输入文件的第一行由两个整数N和K组成，由一个空格间隔。N(1N10000)是仓库里光缆的数目，K(1K10000)是需要的网线数目。接下来的N行每行只有一个实数，告诉你每根缆线的长度(单位：m)。这些网线至少长1m，最多不超过100km。所有的长度精确到cm，且小数点后有且仅有两位。输出格式把你求得的最大网线长度写进输出文件(单位：m)。长度要精确到cm，并且输出时小数点后要恰有两位。如果无论如何也不可能切割出需要数目的网线(每根至少1cm长)，那么就输出“0.00”(不包括引号)。输入样例#14 118.027.434.575.39输出样例#12.00解题思路二分答案，由于切割出的网线需要至少1cm长，故输入优化并将网线长度转换为cm进行二分答案避免浮点数操作的精度问题。参考代码#includeusing namespace std;const int maxn=10000+20;int n,k,amaxn;char str20;int read()/字符串读入长度，转化为cm输出scanf(%s,str);int i,ans=0,len=strlen(str);for(i=0;ilen;i+)if(stri=.)continue;ans*=10;ans+=stri-0;return ans;int check(int m)/计算m长度能切割出多少根网线int i,ans=0;if(m=0)return 0;for(i=1;i=k)return 1;else return 0;int main()int i,j,ans=0,l,r=0,mid;scanf(%d%d,&n,&k);for(i=1;i=n;i+)ai=read();r=max(r,ai);l=0;while(l=r)mid=(l+r)/2;if(check(mid)ans=mid;l=mid+1;else r=mid-1;printf(%.2lfn,ans*1.0/100);return 0;3. 和为给定数【by 】来源：/ch0111/07/问题描述给出若干个整数，询问其中是否有一对数的和等于给定的数。输入格式共三行：第一行是整数n(0 n = 100,000)，表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第三行是一个整数m（0 = m = 230)，表示需要得到的和。输出格式若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。输入样例#142 5 1 46输出样例#11 5解题思路先将n个数排序，遍历每个数，二分它后面的数，相加若能得到给定数即可参考代码#includeusing namespace std;const int MAXN=100050;int aMAXN;int main()int n,i,m,mid,l,r,flag;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);scanf(%d,&m);sort(a+1,a+n+1);for(i=1;i=n;i+)l=i+1;r=n;flag=0;while(lm)r=mid-1;else l=mid+1;if(flag)break;if(flag)printf(%d %dn,ai,amid);else printf(Non);return 0;4. 区间合并【by 】来源：/ch0204/7620/问题描述给定 n 个闭区间 ai; bi，其中i=1,2,.,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，1;2 和 2;3 可以合并为 1;3，1;3 和 2;4 可以合并为 1;4，但是1;2 和 3;4 不可以合并。我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。输入格式第一行为一个整数n，3 n 50000。表示输入区间的数量。之后n行，在第i行上（1 i n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 ai; bi（其中 1 ai bi 10000）。输出格式输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。输入样例#155 61 510 106 98 10输出样例#11 10解题思路1使用基数排序（桶排）思想，每段区间*2设置为1（1,23,4变为2,4,6,8），则全部设置完毕后，若最大区间minl*2,maxr*2中若有0，则无法合并。最大时间复杂度O(50000*20000)超时。参考代码1#includeusing namespace std;const int maxn=20000+50;/最大区间右端点小于10000int amaxn;int main()int n,l,r,i,j,minl=maxn,maxr=0;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d%d,&l,&r);minl=min(minl,l);maxr=max(maxr,r);for(j=2*l;j=2*r;j+)aj=1;int flag=1;for(i=2*minl;i=2*maxr;i+)if(ai=0)flag=0;break;if(flag)printf(%d %dn,minl,maxr);else printf(non);return 0;解题思路2仍使用上题策略，由于存在区间更新，可使用差分数组优化时间复杂度O(n)参考代码2#includeusing namespace std;const int maxn=20000+50; /最大区间右端点小于10000int amaxn;int main()int n,l,r,i,j,minl=maxn,maxr=0;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d%d,&l,&r);minl=min(minl,l);maxr=max(maxr,r);a2*l+=1;a2*r+1+=-1;int flag=1;for(i=2*minl;i=2*maxr;i+)ai+=ai-1+ai;if(ai=0)flag=0;break;if(flag)printf(%d %dn,minl,maxr);else printf(non);return 0;解题思路3快排，以左边界为第一关键字，右边界为第二关键字升序排列，然后遍历n个区间，同时更新最大区间，若存在一个区间的左边界大于最大区间的有边界则无法合并时间复杂度O(n)参考代码3#includeusing namespace std;const int maxn=50000+50;struct areaint l,r;amaxn;int cmp(area x,area y)if(x.l=y.l)return x.ry.r;else return x.ly.l;int main()int n,i,flag=1;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d%d,&ai.l,&ai.r);sort(a+1,a+n+1,cmp);int l=a1.l,r=a1.r;for(i=2;ir)flag=0;break;r=max(r,ai.r);if(flag)printf(%d %dn,l,r);else printf(no);return 0;7.8 宽度优先搜索1. 产生数【by 】来源：/problem/show?pid=1037问题描述给出一个整数 n（n1030) 和 k 个变换规则（k536上面的整数 234 经过变换后可能产生出的整数为（包括原数）:234 534 264 564 共 4 种不同的产生数问题：给出一个整数 n 和 k 个规则。求出：经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。输入格式键盘输人，格式为：n k x1 y1 x2 y2 . xn yn输出格式屏幕输出，格式为：一个整数（满足条件的个数）输入样例#1234 22 53 6输出样例#14解题思路1暴力宽搜40%参考代码1#includeusing namespace std;const int maxn=2000+5;const int maxk=15+5;int nummaxk,tomaxkmaxk;int ans=0,len;queueq;set vis;string n;int main()int k,i,j,x,y;cinn;scanf(%d,&k);for(i=1;i=k;i+)scanf(%d%d,&x,&y);numx+;toxnumx=y;len=n.length();q.push(n);ans+;vis.insert(n);while(!q.empty()string u=q.front();q.pop();for(i=0;ilen;i+)for(j=1;j=numui-0;j+)string v=u;vi=tovi-0j+0;if(!vis.count(v)vis.insert(v);q.push(v);ans+;printf(%dn,ans);解题思路2100%高精+乘法原理乘法原理，查看每一个位数通过规则所能到达的数的个数，相乘就是答案。参考代码2#includeusing namespace std;int vis1515,a100;string n;void floyd()int i,j,k;for(k=0;k=9;k+)for(i=0;i=9;i+)for(j=0;j=9;j+)if(visik&viskj)visij=1;void mul(int d)int i,len;for(i=1;i=a0;i+)ai*=d;for(i=1;i=1;i-)printf(%d,ai);printf(n);int main()int k,i,j,x,y,cnt;cinn;scanf(%d,&k);for(i=1;i=k;i+)scanf(%d%d,&x,&y);visxx=visxy=1;floyd();a0=a1=1;int len=n.length();for(i=0;ilen;i+)cnt=0;for(j=0;j=9;j+)if(visni-0j)cnt+;if(cnt)mul(cnt);print();return 0;1. 奇怪的电梯【by 】/problem/show?pid=1135 问题描述呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？输入格式输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200, 1A,BN)，第二行为N个用空格隔开的正整数，表示Ki。输出格式输出文件仅一行，即最少按键次数,若无法到达，则输出-1。输入样例#15 1 53 3 1 2 5输出样例#13解题思路aij表示i能到达j注意点：输入数据A、B可能相等参考代码#includeusing namespace std;const int maxn=200+20;int amaxnmaxn;int vismaxn;int n,A,B;queueq;int main()int i,k,u,v,flag;scanf(%d%d%d,&n,&A,&B);if(A=B)printf(0n);return 0;for(i=1;i=1)aii-k=1;if(i+k=n)aii+k=1;q.push(A);visA=1;flag=0;while(!q.empty()u=q.front();q.pop();for(v=1;v=n;v+)if(auv)if(!visv)visv=visu+1;if(v=B)flag=1;break;q.push(v);if(flag)break;if(!flag)printf(-1n);else printf(%dn,visB-1);return 0;3. 家庭问题【by 】来源（/oj/#main/show/1127) 问题描述有n个人，编号为1,2,n，另外还知道存在K个关系。一个关系的表达为二元组（，）形式，表示，为同一家庭的成员。当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？例如：n6，k3，三个关系为（1,2），(1,3)，(4,5)此时，6个人组成三个家庭，即：1,2,3为一个家庭，4,5为一个家庭，6单独为一个家庭，第一个家庭的人数为最多。输入格式第一行为n,k二个整数（1n100，0=k=1000）（用空格分隔）。接下来的k行，每行二个整数（用空格分隔）表示关系。输出格式二个整数（分别表示家庭个数和最大家庭人数）。输入样例#16 31 21 34 5输出样例#13 3解题思路联通块计数问题参考代码#includeusing namespace std;const int maxn=100+20;int amaxnmaxn,vismaxn;int n,k,cnt,tot,ans;queueq;void bfs(int i)int u,v;q.push(i);visi=+tot;while(!q.empty()u=q.front();q.pop();for(v=1;v=n;v+)if(auv)if(!visv)visv=+tot;q.push(v);int main()int i,u,v;scanf(%d%d,&n,&k);for(i=1;i=k;i+)scanf(%d%d,&u,&v);auv=avu=1;cnt=0;ans=0;for(i=1;i=n;i+)if(!visi)cnt+;tot=0;bfs(i);ans=max(ans,tot);printf(%d %dn,cnt,ans);return 0;7.9深度优先搜索2. 迷宫【by 】来源：/oj/#main/show/1167问题描述设有一个N*N(2=N10)方格的迷宫，入口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通，1，表示不能通过，入口和出口肯定是0。迷宫走的规则如下：即从某个点开始，又八个方向可走，前进方格中的数字为0时表示可以通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径（不能重复），输出路径总数，如果无法到达，则输出0。输入格式第一行输入N.接下来N行，每行N个数字，0或1，描述迷宫。输出格式输出路径总数。输入样例#130 0 00 1 11 0 0输出样例#12解题思路参考代码#includeusing namespace std;const int maxn=10+5;int amaxnmaxn,vismaxnmaxn;int n,cnt;void dfs(int ui,int uj)int i,j,vi,vj;if(ui=1&uj=n)cnt+;return;for(i=-1;i=1;i+)for(j=-1;j=1;j+)if(i=0&j=0)continue;vi=ui+i;vj=uj+j;if(vi1|vjn|vjn)continue;if(!visvivj&!avivj)visvivj=1;dfs(vi,vj);visvivj=0;int main()int i,j;scanf(%d,&n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&aij);vis11=1;cnt=0;dfs(1,1);printf(%dn,cnt);return 0;3. 数的划分【by 】来源：/oj/#main/show/1187问题描述把正整数N分解成M个正整数的和，M个加数相同但顺序不同认为是相同的方案，要求总方案数。如3=1+2跟3=2+1是两个相同的方案。输入格式第一行输入两个整数N,M(1=M=N=50)。输出格式输出一个整数表示方案数。输入样例#15 3输出样例#12解题思路参考代码#includeusing namespace std;const int maxn=50+5;int amaxn;int m,n,cnt;void dfs(int cur,int tot)int i,j,ok;if(cur=m+1)if(tot=n)cnt+;return;for(i=1;in)continue;/剪枝 ok=1;for(j=1;jaj)ok=0;break;if(ok)acur=i;dfs(cur+1,tot+i);int main()scanf(%d%d,&n,&m);cnt=0;dfs(1,0);printf(%dn,cnt);return 0;4.素数环【by 】来源：/oj/#main/show/1153问题描述输入n(2=n=20),把1到n这n个数摆成一个环，要求相邻的两个数的和是一个素数。输出任意一个合法答案。输入格式输入一行一个数n。输出格式输出1到n的一个排列，表示一个环。如果无解，则输出-1。输入样例#14输出样例#11 2 3 4解题思路参考代码#includeusing namespace std;const int maxn=20+5;int amaxn,vismaxn,isprimemaxn*2;int n,flag=0;void init()for(int i=2;i*i=49;i+)if(!isprimei)for(int j=i*i;j=49;j+=i)isprimej=1;isprime1=1;void dfs(int cur)if(flag)return;if(cur=n)if(!isprimea0+an-1)for(int i=0;i=n-1;i+)printf(%d ,ai);printf(n);flag=1;return;for(int i=2;i=n;i+)if(!visi&!isprimeacur-1+i)visi=1;acur=i;if(!flag)dfs(cur+1);visi=0;int main()scanf(%d,&n);if(n%2)printf(-1);/n若为奇数，必有2个偶数在一起 elseinit();a0=1;vis1=1;dfs(1);if(!flag)printf(-1);return 0;7.10动态规划2. 最大连续子序列和【by 】来源：/oj/#main/show/1151问题描述 给定一个长度为n的序列，求该序列的最大的连续子序列和。输入格式第一行一个整数n。第2行n个整数，表示该序列。输出格式一个整数，表示该序列的最大连续子序列和。输入样例#1102 5 -3 4 -9 -2 6 1 -8 7输出样例#18数据范围1n1000000，|序列每个元素|1000。解题思路令dpi表示前i个数且必须包含i的最大连续和。则有：dpi=max(ai,dpi-1+ai);参考代码#includeusing namespace std;const int maxn=1000000+50;int n,amaxn,dpmaxn,ans; int main()int i;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);ans=dp1=a1;for(i=2;i=n;i+)dpi=max(ai,dpi-1+ai);ans=max(ans,dpi);printf(%dn,ans);return 0;3. 最长不下降子序列【by 】来源：/oj/#main/show/1146问题描述给定一个n个数的序列A，问最长的不下降子序列长度为多少。对于一个序列p1 p2 pk,其为不下降子序列需要满足：Ap1 = Ap2 = Ap3 = = Apk。输入格式第一行一个整数n。接下来一行n个整数，表示Ai。输出格式一个整数，表示最长的不下降子序列的长度。输入样例#171 7 3 5 9 4 8输出样例#14数据范围n = 5000,|Ai|=1000000。解题思路令dpi表示第i个数在前i个数中的序列长度参考代码#includeusing namespace std;const int maxn=5000+50;int n,amaxn,dpmaxn,ans; int main()int i,j,maxl;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);dpi=1;ans=1;for(i=2;i=n;i+)maxl=0;for(j=1;ji;j+)if(aj=ai)maxl=max(maxl,dpj);dpi=maxl+1;ans=max(ans,dpi);printf(%dn,ans);return 0;4. 最长公共子序列【by 】来源：/oj/#main/show/1147问题描述给定两个小写字母组成的字符串S,T，问S与T的最长公共子序列。输入格式第一行一个字符串，表示字符串S。第二行一个字符串，表示字符串T。输出格式一个整数，表示最长的公共子序列长度。输入样例#1bbabxbcbatxbbc输出样例#15数据范围1=|S|,|T|=5000解题思路参考代码#includeusing namespace std;const int maxn=5000+50;char smaxn,tmaxn;int dpmaxnmaxn; int main()int i,j,len1,len2;scanf(%s,s);scanf(%s,t);len1=strlen(s);len2=strlen(t);for(i=1;i=len1;i+)for(j=1;j=len2;j+)if(si-1=tj-1)dpij=dpi-1j-1+1;else dpij=max(dpi-1j,dpij-1);print