一开始知道应该动态规划 但是不知道转移方程该怎么写 想了一会儿之后想到一个法子 但没证明正确性

具体内容就是:

第一次遍历字符串 得到每个字符的出现次序 将其当作他们各自对应的权值 所以对于一个字符串PGBHGBP就可以看成1234231

第二次遍历字符串 用一个栈来记录权值严格递增序列 每当向后增加了一个递增序列 意味着必须多一次涂色, 例如:

原来的栈是123 又进来一个4 栈此时向后增加一个变成了1234 意味着必须多一次涂色才能涂出来4 因此ans++ 原来的栈是123 此时进来了一个2 栈就退两次栈 然后把2填入 这个操作的含义大概是 新加入的2这个和原来的2可以相当于画到一起 即1222然后画上一笔3变成1232 但是3就显然被隔离开来了 将栈中的3退栈就对应着它被隔离开来了

所以总体来说直接维护一个严格单调递增栈 然后统计这个栈被延长了多少次就相当于最少画多少笔

说的很乱 因为我自己都不知道这个做法到底是不是严格正确的 但最终的结果是拿了90pts... 所以首先想知道这个做法为啥能对这么多个点 然后想知道错掉的#3是少考虑了什么情况

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<vector>
#include <string>
#include <stack>
using namespace std;

string s;
int w[256];

int main() {
	cin >> s;
	int wtop = 1;
	for (int i = 0; i < s.size(); i++) {
		if (w[s[i]])
			continue;
		w[s[i]] = wtop++;
	}
	stack<char> st;
	st.push(0);			// 栈底垫上一个0  之后栈就不会空了
	int ans = 0;
	for (int i = 0; i < s.size(); i++) {
		if (w[st.top()] >= w[s[i]]) {	// 严格递增序列未被延长 说明前面有相同颜色可以一路画过来
			while (w[st.top()] >= w[s[i]]) 
				st.pop();
		}
		else {	// 严格递增序列被延长 必须多画一笔
			ans++;
		}
		st.push(s[i]);
	}
	cout << ans;
	return 0;
}