/* 我对题目2的思路： 根据每个字母的约束条件，找到满足条件的最长子串，答案就是长度减去这个最长子串的长度。 */ #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int MAX = 100010; char str[MAX]; int invalid[30][30], dp[26]; int main() { int n, m; while (scanf("%d", &n) != EOF){ scanf("%s", str); scanf("%d", &m); memset(invalid, 0, sizeof(invalid)); memset(dp, 0, sizeof(dp)); for (int i = 0; i<m; i++){ char ch1, ch2; getchar(); scanf("%c%c", &ch1, &ch2); invalid[ch1 - 'a'][ch2 - 'a'] = invalid[ch2 - 'a'][ch1 - 'a'] = 1; } for (int i = 0; i<n; i++){ char a = str[i]; int tmp = 1; for (int j = 0; j<26; j++){ if (invalid[a - 'a'][j]) continue; tmp = max(tmp, dp[j] + 1); } //printf("%d ", tmp); dp[a - 'a'] = tmp; } sort(dp, dp + 26); printf("%d\n", n - dp[25]); } } /* 我对题目3的思路： 用队列模拟注册流程，需要判断到达时间，决定办理先后顺序 */ #include <iostream> #include <vector> #include <queue> using namespace std; const int N = 10010; const int INF = 0x3f3f3f3f; int n, m, k; struct node { int now; //arrive time Ti int id; //student number Si; int index; int len; //visit number of Pi offices int v; //index vector<int> s; //Oij offices vector<int> t; //Wij processing time node(){ now = id = index = len = v = 0; }; }; node *pNode[N]; int res[N], beg[105]; struct mycmp { bool operator()(node *a, node *b){ if (a->now == b->now) return a->id > b->id; return a->now>b->now; } }; priority_queue<node*, vector<node*>, mycmp> q; int main() { scanf("%d %d %d", &n, &m, &k); for (int i = 0; i<n; i++){ int num; //num is Pi offices pNode[i] = new node(); scanf("%d %d %d", &pNode[i]->id, &pNode[i]->now, &num); pNode[i]->v = i; pNode[i]->len = num; int a, b; //Oij and Wij for (int j = 0; j<num; j++){ scanf("%d %d", &a, &b); pNode[i]->s.push_back(a); pNode[i]->t.push_back(b); } pNode[i]->index = 0;//start from first office pNode[i]->now += k;//from gate to first office q.push(pNode[i]); } while (!q.empty()){ node *tmp = q.top(); q.pop(); int b = max(tmp->now, beg[tmp->s[tmp->index]]); tmp->now = beg[tmp->s[tmp->index]] = b + tmp->t[tmp->index]; if (tmp->index == tmp->len - 1){ //end of registration res[tmp->v] = tmp->now; } else{ tmp->now += k;//from one office to another tmp->index++; q.push(tmp); } } for (int i = 0; i<n; i++) printf("%d\n", res[i]); return 0; }