uva 1481-Genome Evolution(暴力)
963 ワード
タイトルリンク:uva 1481-Genome Evolution
2つの長さnの集合を与え,2つの集合に同じ連続サブ集合がどれだけ存在するかを問う.
解題構想:暴力列挙、第1の集合を記録し、第2の集合は各数の出現位置を記録し、サブ集合の大きさは不定であるが、必ず1より大きいので、第1の集合を列挙し、r-l+1==kが現れた場合(rは現在のサブ集合の中で第2の集合の中で最も右の位置であり、lは最も左の位置であり、kは列挙の個数である)、ans++である.
2つの長さnの集合を与え,2つの集合に同じ連続サブ集合がどれだけ存在するかを問う.
解題構想:暴力列挙、第1の集合を記録し、第2の集合は各数の出現位置を記録し、サブ集合の大きさは不定であるが、必ず1より大きいので、第1の集合を列挙し、r-l+1==kが現れた場合(rは現在のサブ集合の中で第2の集合の中で最も右の位置であり、lは最も左の位置であり、kは列挙の個数である)、ans++である.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 3005;
int n, v[N], a[N];
void init() {
int k;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) {
scanf("%d", &k);
v[k] = i;
}
}
int solve() {
int l, r, k, ans = 0;
for (int i = 0; i < n; i++) {
l = r = v[a[i]]; k = 1;
for (int j = i + 1; j < n; j++) {
l = min(l, v[a[j]]);
r = max(r, v[a[j]]);
k++;
if (r - l + 1 == k) ans++;
}
}
return ans;
}
int main() {
while (scanf("%d", &n) == 1 && n) {
init();
printf("%d
", solve());
}
return 0;
}