PAT (Advanced Level) Practice - 1045 Favorite Color Stripe（30 分）-阿里云开发者社区

PAT (Advanced Level) Practice - 1045 Favorite Color Stripe（30 分）

2022-05-21 82

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： PAT (Advanced Level) Practice - 1045 Favorite Color Stripe（30 分）

题目链接：点击打开链接

题目大意：略。

解题思路：找规律：row，col 都从 1 开始，外围为 0；当前位置填入的值val = max(相邻左，相邻上)，如果 like[i] == give[j]，val = ++ma，否认 val = ma。

		2	2	4	1	5	5	6	3	1	1	5	6
	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	2	2	2	2	2	2	2	2	2	2	2
3	0	1	2	2	2	2	2	2	3	3	3	3	3
1	0	1	2	2	3	3	3	3	3	4	5	5	5
5	0	1	2	2	3	4	5	5	5	5	5	6	6
6	0	1	2	2	3	4	5	6	6	6	6	6	7

注意：WA 代码与 AC 代码区别是：WA代码先手动初始化（1，1）开始，再自动填充；而AC代码是利用外围的（0，0）直接自动填充；如图所示有一种情况WA代码（码如其名）：

AC 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintM=210, L=1e4+10;
intlike[M], give[L], rsrr[M][L];
intmain()
{
intn,m,l,ma;
scanf("%d%d",&n,&m);
for(inti=1;i<=m;i++) scanf("%d",&like[i]);
scanf("%d",&l);
for(inti=1;i<=l;i++) scanf("%d",&give[i]);
for(inti=1;i<=m;i++)
    {
for(intj=1;j<=l;j++)
        {
ma=max(rsrr[i-1][j],rsrr[i][j-1]);
if(like[i]==give[j]) rsrr[i][j]=++ma;
elsersrr[i][j]=ma;
        }
    }
printf("%d\n",ma);
return0;
}

WA 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintM=210, L=1e4+10;
intlike[M], give[L], rsrr[M][L];
intmain()
{
intn,m,l,ma;
scanf("%d%d",&n,&m);
for(inti=1;i<=m;i++) scanf("%d",&like[i]);
scanf("%d",&l);
for(inti=1;i<=l;i++) scanf("%d",&give[i]);
intth=0;
for(inti=1;i<=l;i++)
if(like[1]==give[i]) rsrr[1][i]=++th;
elsersrr[1][i]=th;
for(inti=1;i<=m;i++) rsrr[i][1]=rsrr[1][1];
for(inti=2;i<=m;i++)
    {
for(intj=2;j<=l;j++)
        {
ma=max(rsrr[i-1][j],rsrr[i][j-1]);
if(like[i]==give[j]) rsrr[i][j]=++ma;
elsersrr[i][j]=ma;
        }
    }
printf("%d\n",ma);
return0;
}

PAT (Advanced Level) Practice - 1045 Favorite Color Stripe（30 分）

热门文章

最新文章

相关电子书

		2	2	4	1	5	5	6	3	1	1	5	6
	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	2	2	2	2	2	2	2	2	2	2	2
3	0	1	2	2	2	2	2	2	3	3	3	3	3
1	0	1	2	2	3	3	3	3	3	4	5	5	5
5	0	1	2	2	3	4	5	5	5	5	5	6	6
6	0	1	2	2	3	4	5	6	6	6	6	6	7

		2	2	4	1	5	5	6	3	1	1	5	6
	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	2	2	2	2	2	2	2	2	2	2	2
3	0	1	2	2	2	2	2	2	3	3	3	3	3
1	0	1	2	2	3	3	3	3	3	4	5	5	5
5	0	1	2	2	3	4	5	5	5	5	5	6	6
6	0	1	2	2	3	4	5	6	6	6	6	6	7

		2	2	4	1	5	5	6	3	1	1	5	6
	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	2	2	2	2	2	2	2	2	2	2	2
3	0	1	2	2	2	2	2	2	3	3	3	3	3
1	0	1	2	2	3	3	3	3	3	4	5	5	5
5	0	1	2	2	3	4	5	5	5	5	5	6	6
6	0	1	2	2	3	4	5	6	6	6	6	6	7