现在给出了一个由数字 0 和 1 组成的序列𝐴,它可能不是一个交错序列,但是你可以从这个 序列中选择一些数字出来,按他们在序列𝐴中原有的相对顺序排列(即选取𝐴的一个子序列), 使得你最后得到的是一个交错序列。问这样能得到的交错序列的最长长度是多少。
数据范围: ,序列中只包含 0 和 1。
第一行包含一个整数𝑛,表示输入序列的长度。第二行包含 𝑛 个 0 或 1,表示对应的序列。
输出能够得到的最长交错序列的长度。
3 0 1 0
3
8 1 1 0 0 1 1 0 0
4
#include <stdio.h>
#define maxn 100005
int n,a[maxn];
int main(){
int i,res;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
res=1;
for(i=1;i<n;i++){
if(a[i-1]!=a[i])
res++;
}
printf("%d\n",res);
return 0;
}
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; int count = 1; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); if (i > 0) { if (arr[i] != arr[i - 1]) { count++; } } } System.out.println(count); } }
#注意题目并不要求连续子串,即数字发生变化长度就加 1 ,只要记录输入序列数字变化了几次即可 #include <iostream> using namespace std; int main() { int mid,mid2,count=1; int length,l=1; cin>>length; cin>>mid; while(l!=length) { l++; cin>>mid2; if(mid2!=mid) { count++; } mid=mid2; } cout<<count<<endl; return 0; }
#include <iostream> using namespace std; int main(void) { int len, count = 1; cin >> len; int a, b; cin >> a; for (int i = 0; i < len-1; i++) { cin >> b; if (a != b) count++; a = b; } cout << count << endl; return 0; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @author wylu */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); br.readLine(); String[] strs = br.readLine().split(" "); int res = 1, cur = strs[0].charAt(0) - '0'; for (int i = 1; i < strs.length; i++) { if(strs[i].charAt(0) - '0' == cur) continue; res++; cur = strs[i].charAt(0) - '0'; } System.out.println(res); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); int[] in = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray(); int[][] dp = new int[2][2]; for (int i =1; i<=n; i++) { int x = in[i-1]; int rx = (in[i-1] + 1) % 2; dp[i%2][x] = Math.max(dp[(i-1)%2][rx]+1, dp[(i-1)%2][x]); dp[i%2][rx] = dp[(i-1)%2][rx]; } System.out.println(Math.max(dp[n%2][0], dp[n%2][1])); } }
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for(int i = 0; i < n; i++) { cin>>v[i]; } int pre = v[0]; int ans = 1; for(int i = 1; i < n; i++) { if(pre != v[i]) { ans++; pre = (pre+1) % 2; } } cout<<ans; return 0; }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case int n = in.nextInt(); // 个数 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = in.nextInt(); } int cur = nums[0]; int res = 1; for (int i = 1; i < n; i++) { if (nums[i] == cur) continue; cur = nums[i]; res++; } System.out.println(res); } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = Integer.parseInt(in.nextLine()); ArrayList<Integer> list = new ArrayList<>(); int len = 1; for(int i=0; i<n; i++){ list.add(in.nextInt()); } int pre = list.get(0); for(int i=1; i<n; i++){ if(list.get(i) != pre){ len++; pre = list.get(i); } } System.out.println(len); } }
#include<bits/stdc++.h> using namespace std; int main() { int n,sum=0;cin>>n; vector<int> v(n);cin>>v[0]; for(int i=1;i<n;i++) { cin>>v[i]; if(v[i]!=v[i-1]) sum++; } cout<<sum+1; }
let n=readline() let input=readline() function solve(n, input) { let arr = input.split(' ').map(Number) let pre = arr[0] let cnt = 1 for (let i = 1; i < arr.length; i++) { if (arr[i] != pre) { cnt++ pre = arr[i] } } console.log(cnt) } solve(n, input)
// 没通过 超了,但就是想留着 let n = '3' let input = "1 1 0 0 1 1 0 0" function solve(n, input) { let arr = input.split(' ').map(Number) if (arr.length > 1) { let ans = recursion(arr, arr[0]) console.log(ans) }else{ console.log(0) } } function recursion(arr, num) { if (arr.indexOf(num) === -1) { return 0 } else { let index = arr.indexOf(1 - num) arr = arr.slice(index) return 1 + recursion(arr, 1 - num) } } solve(n, input)
#include<iostream> #include<vector> #include<string> using namespace std; int main() { int a; cin>>a; int b; int count=1; vector<int>vec; for(int i=0;i<a;i++) { cin>>b; vec.push_back(b); if(i>=1) { if(vec[i]!=vec[i-1]) { count++; } } } cout<<count<<endl; return 0; }