PAT (Advanced Level) Practice - 1045 Favorite Color Stripe(30 分)
发布日期:2021-06-30 23:43:16
浏览次数:2
分类:技术文章
本文共 1902 字,大约阅读时间需要 6 分钟。
题目链接:
题目大意:略。
解题思路:找规律: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#include #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int M=210, L=1e4+10;int like[M], give[L], rsrr[M][L];int main(){ int n,m,l,ma; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&like[i]); scanf("%d",&l); for(int i=1;i<=l;i++) scanf("%d",&give[i]); for(int i=1;i<=m;i++) { for(int j=1;j<=l;j++) { ma=max(rsrr[i-1][j],rsrr[i][j-1]); if(like[i]==give[j]) rsrr[i][j]=++ma; else rsrr[i][j]=ma; } } printf("%d\n",ma); return 0;}
WA 代码
#include#include #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int M=210, L=1e4+10;int like[M], give[L], rsrr[M][L];int main(){ int n,m,l,ma; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&like[i]); scanf("%d",&l); for(int i=1;i<=l;i++) scanf("%d",&give[i]); int th=0; for(int i=1;i<=l;i++) if(like[1]==give[i]) rsrr[1][i]=++th; else rsrr[1][i]=th; for(int i=1;i<=m;i++) rsrr[i][1]=rsrr[1][1]; for(int i=2;i<=m;i++) { for(int j=2;j<=l;j++) { ma=max(rsrr[i-1][j],rsrr[i][j-1]); if(like[i]==give[j]) rsrr[i][j]=++ma; else rsrr[i][j]=ma; } } printf("%d\n",ma); return 0;}
转载地址:https://lux-sun.blog.csdn.net/article/details/82109373 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月19日 22时06分09秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python一键获取微信推送封面图
2019-04-30
油猴脚本:微信推送浏览功能拓展
2019-04-30
JavaScript DOM对象操作详解
2019-04-30
JavaScript 表单操作与MD5加密
2019-04-30
JAVA学习笔记4 - 循环与分支结构
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
JAVA学习笔记8 - Stream 和 File I/O
2019-04-30
JAVA学习笔记9 - 异常
2019-04-30
JAVA学习笔记10 - 继承
2019-04-30
JAVA学习笔记11 - 接口interface
2019-04-30
JAVA学习笔记12 - 包package
2019-04-30
Android 开发学习笔记 00 - Getting Started
2019-04-30
【学习笔记】Android Activity
2019-04-30
Android使用Retrofit_00_Getting Started
2019-04-30
Android使用Retrofit_01_OAuth2 + GitHub
2019-04-30
Django + REST学习笔记
2019-04-30