关键词：
题目
Alice writes an English composition with a length of N characters. However, her teacher requires that M illegal pairs of characters cannot be adjacent, and if ‘ab‘ cannot be adjacent, ‘ba‘ cannot be adjacent either.
In order to meet the requirements, Alice needs to delete some characters.
Please work out the minimum number of characters that need to be deleted.
给定一个由小写字母组成的字符串，规定某些字符不能相邻。求最少需要删除多少个字符使得剩下的字符串中不存在那些规定不能相邻的字符相邻。
解法
字符串中的字符只有26种可能，去除某些字符剩余的字符串只能以a-z这些字符结尾，如果记录 dp[c]表示以 字符 c+‘a‘ 结尾的字符串的最长长度，则可以有递推公式
dp[ch] = max(dp[ch], dp[t] + 1) t为a-z，且t和ch可以相邻。这样，在从头到尾扫描完一遍字符串，得到dp数组之后，最少需要删除的字符的个数就等于 n(原来字符串长度) - max(dp[c]).
#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<functional>
#include<queue>
#include<vector>
#include<set>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<stack>
#include<map>
#include<algorithm>
#include<string.h>
using namespace std;
char str[1000005];
int dp[26];
int n;
bool table[26][26];
int main(){
scanf("%d", &n);
scanf("%s", str);
memset(dp, -1, sizeof(dp));
int k;
scanf("%d", &k);
char word[4];
for (int i = 0; i < k; i++){
scanf("%s", word);
table[word[0] - ‘a‘][word[1] - ‘a‘] = true;
table[word[1] - ‘a‘][word[0] - ‘a‘] = true;
}
for (int i = 0; i < n; i++){
int cur = str[i] - ‘a‘;
int tmp = 1;
for (int j = 0; j < 26; j++){
if (table[cur][j])
continue;
tmp = max(tmp, dp[j] + 1);
}
dp[cur] = tmp;
}
int tmp = 0;
for (int i = 0; i < 26; i++)
tmp = max(tmp, dp[i]);
printf("%d
", n - tmp);
return 0;
}
小米2017校招笔试题
只过了20%...我日树的高度 时间限制：C/C++语言1000MS；其他语言3000MS 内存限制：C/C++语言65536KB；其他语言589824KB 题目描述： 现在有一棵合法的二叉树，树的节点都是用数字表示， 现在给定这棵树上所有的父子关系，求这棵树的高... 查看详情
lgyx2017校招笔试题
前言今天通知过了笔试，但总感觉有些笔试没来得及做的题不解决不舒服斯基。题目 大意就是，给你个形如a,b,c,ab,bb,cb,ac,bc,cc,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......按某种规律排列的无限长的字符串数组，要求：1）给定一个位置，... 查看详情
网易2017年校招笔试题最大的奇约数
题目：定义函数f(x)为x的最大奇数约数，x为正整数，例如f(44)=11.现在给出一个N,需要求出f(1)+f(2)+f(3)+...+f(N)例如：N=7f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+7=21. 分析：奇数的最大约数是自身，偶数的最大约数是是除去所有偶因子之... 查看详情
奇虎3602017校招笔试题
最强大脑时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言65536KB；其他语言589824KB题目描述：小B乘火车和朋友们一起在N市到M市之间旅行。她在路途中时睡时醒。当她醒来观看窗外的风景时，注意到每个火车站都有一... 查看详情
校招笔试题大杂烩
1、某表达式的前缀形式为"+-*^ABCD/E/F+GH",运算符优先级为^>*/>-+,它的中缀形式为(C)A A^B*C-D+E/F/G+H B A^B*(C-D)+(E/F)/G+H C A^B*C-D+E/(F/(G+H)) D A^B*(C-D)+ 查看详情
快手2019校招笔试题(代码片段)
目的：分别从前面和后面开始找划分点，使得前面的数字之和=后面的数字之和目标表述：sum(前面m个数)=sum(后面n个数）s.t.m+n<=N（总个数）变形：sum[i]表示前i个数之和，sum2[i]表示后i... 查看详情
1~n的全排列--阅文集团2018校招笔试题
题目大意：给定整数n，求出1~n的全排列示例输入：n=3输出：[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]1importjava.util.Scanner;2importjava.util.ArrayList;34publicclassMain{5privatevoidfunc(ArrayList<Integer>nArray,Arra 查看详情
兆易创新9月校招笔试题_ic设计/验证
还有器件岗位的笔试题：1、CMOS中哪些制造步骤中用到了离子注入，需要注意哪些？2、有哪些薄膜制备方法？各有什么优缺点？3、COMS的制作步骤，简要叙述。4、载流子的输运方式有哪些，简要叙... 查看详情
天上掉馅饼--移动研究院2018校招笔试题
题目：天上掉馅饼时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言131072KB；其他语言655360KB题目描述：大家都知道“天上不会掉馅饼”这句话，但是有一天，小明在回学校的路上，天上还真掉起了馅饼。小明的人品实... 查看详情
网易2019校招笔试题-瞌睡(代码片段)
分析：由于小易清醒的时间是连续的，所以整个搜索空间为O(n)，根本不需要贪心或者动态规划就能搞定。小易这堂课获得的兴趣值分为两部分：本来就清醒时获得的兴趣值，被叫醒的k分钟获得的兴趣值。因为... 查看详情
阿里巴巴2016校招笔试题（含答案解析）(代码片段)
3、将1,2,3,……,99,100任意排列成一个圈，相邻两数的差的绝对值求和最多为（）A：100B：198C：200D：500E：2500F：5000答案：F4、如果下列的公式成立：84*148=B6A8。则采用的是（&# 查看详情
快手2019校招笔试题(代码片段)
目的：分别从前面和后面开始找划分点，使得前面的数字之和=后面的数字之和目标表述：sum(前面m个数)=sum(后面n个数）s.t.m+n<=N（总个数）变形：sum[i]表示前i个数之和，sum2[i]表示后i... 查看详情
网易2017秋招笔试题3：最长公共子括号序列长度
【问题来源】网传的2017网易秋招笔试题【问题描述】 【算法思路】 下面的解题思路摘自 http://www.cnblogs.com/Atanisi/p/7500186.html刚看到题我就想到暴力解，深搜出所有合法的括号序列，再依次比较公共子序列的长度，返... 查看详情
tx2017秋招笔试题之素数对
问题描述：给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。如，输入为10,程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）输入描述:输入包括一个整数n,(3... 查看详情
2017华为优招笔试题
哎，没有接到笔试通知，不知道为啥就错过了。之后见到题目，前两道编程题。其实都见过类似的题目，有点思路，但是直接快速完整实现出来，水平还是达不到。这样的题目，也不算难，三道编程题至少AC两道才算可以。... 查看详情
校招笔试题
题目描述：给出m个字符串S1，S2，...，Sm和一个单独的字符串T。请在T中选出尽可能多的子串同时满足：1）这些子串在T中互不相交。2）这些子串都是S1，S2，...，Sm中的某个串。问最多能选出多少个子串。输入第一行一个数m（1≤... 查看详情
美团2017秋招笔试题拼凑钱币
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。 输入描述:输入包括一个整数n(1≤n≤10000)输出描述:输出一个整数,表示不同的组合方... 查看详情
2017腾讯秋招笔试题之编码
Description： 假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的... 查看详情