A174979.彩带对齐
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
一条长彩带由 n 个等大的方格组成,另一条短彩带由 m 个等大的方格组成。两条彩带的方格都从左到右编号,从 1 开始。每个方格有一个颜色编号,颜色编号相同表示颜色相同。
保持短彩带的方向不变,把它放在长彩带上,使短彩带的每个方格都正好覆盖长彩带的一个方格。短彩带必须完全落在长彩带内。
设短彩带的第 1 格覆盖长彩带的第 s 格,则称 s 为这次摆放的起点。此时短彩带的第 j 格覆盖长彩带的第 s+j−1 格。每对颜色相同的覆盖方格得到 1 分,颜色不同不得分。
请输出一次摆放能得到的最高分,以及有多少个不同起点能得到这个最高分。起点不同就视为不同摆放。
输入格式
第一行包含两个整数 n,m,分别表示长彩带和短彩带的方格数。
第二行包含 n 个整数 a1,a2,…,an,其中 ai 表示长彩带第 i 格的颜色编号。
第三行包含 m 个整数 b1,b2,…,bm,其中 bj 表示短彩带第 j 格的颜色编号。
输出格式
输出一行两个整数,依次表示最高分和达到最高分的不同起点数量,用一个空格隔开。
输入输出样例
输入#1
6 3 1 2 1 2 1 3 1 2 1
输出#1
3 2
输入#2
5 2 4 4 7 4 7 4 7
输出#2
2 2
说明/提示
样例 #1 解释
短彩带有 3 格,合法起点为 1,2,3,4。
| 起点 | 被覆盖的长彩带颜色 | 得分 |
|---|---|---|
| 1 | 1 2 1 | 3 |
| 2 | 2 1 2 | 0 |
| 3 | 1 2 1 | 3 |
| 4 | 2 1 3 | 0 |
最高分为 3,起点 1 和 3 都能达到,共有 2 个。
数据范围
对于所有测试数据,满足:
- 1≤m≤n≤300;
- 1≤ai,bj≤109。
输入解题思路,AI测评打分。不知道怎么写?