codeforeces 780div3 C(dp学不会阿，好菜)

题目 题意: 给定一个字符串，要求删除最少数量的字符，使得字符串满足如下条件。 ① 字符串长度为偶数 ② a[i] = a[i+1], i & 1. 所有字符必须成对出现，aabbccdd这样的。 思路: 1.dp f[i]:表示前i个字符最多能保留的数量 f[i] = max(f[i-1],f[pre[ch]-1]+1). 什么意思哩，就是我这个字符ch默认删除，也可以和上一次出现的同一个ch进行匹配，使得多保留两个。 2.贪心 拿一个桶，记录下当前所有字符的数量。 当ch出现且桶里存在时，将他两个之间的全部删除，然后把桶重置。(怎么像扑克牌里的拖拉机) 怎么证明呢? 首先，根据贪心策略，出现的两个ch之间是不会有两两相同的，因为如果两两相同就会执行操作并且清空桶。而两个ch之间没有两两相同，说明什么呢，只有ch b c d ch d c b这种情况，可以把两个ch删除，使得两个d匹配，但是b和c还是隔着，还是要删除。所以只保留了第二个ch两侧的两个字符，和保留两个ch得到的数量一样。而如果第二个ch两侧不同，那删除两个ch的结果比贪心更差。所以贪心策略即是最优策略，证毕。(感觉在胡言乱语) 时间复杂度: O(n) 或 O(nlogn) 代码:

#include
using namespace std;
typedef long long ll;
typedef pair PII;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i