好看的串数据传输网络最小时延
两道机考题题解整理
题目一：好看的串
题目描述
小华有一个好看的串A。对于一个串，每次可以选择其中任意两个相邻且相同的字符，然后删除其中一个。
例如：
aabbbbaa可以一次操作变成：
abbbbaa aabbbaa aabbbba如果串X可以通过若干次删除操作得到串A，则X也是好看的串。
现在给定目标串A和字符串S，需要计算S中有多少个子串是好看的串。位置不同的相同子串算不同子串。
样例 1
输入：
1 1 a b输出：
0解释：
S中只有一个子串"b"，无法通过删除相邻相同字符得到"a"。
样例 2
输入：
3 6 aab aaabbb输出：
6解释：
目标串A = "aab"，压缩后为：
a:2, b:1所以合法子串必须是若干个连续的a后接若干个连续的b，并且a至少 2 个，b至少 1 个。
合法子串为：
aaab aaabb aaabbb aab aabb aabbb共6个。
题解思路
删除相邻相同字符，只会让某个连续段变短，不会改变连续段的字符顺序，也不会让某一段完全消失。
所以先把目标串A按连续字符压缩。
例如：
A = aab压缩成：
字符段：a b 长度： 2 1一个子串合法，当且仅当：
- 子串的连续字符段序列和
A一样； - 子串每一段长度都大于等于
A对应段长度。
然后枚举S的所有子串，用indx表示当前匹配到目标串的第几段，用cnt表示当前段长度。
代码
#include<iostream>#include<vector>#include<string>usingnamespacestd;string A,S;intn,m;intmain(){cin>>n>>m>>A>>S;vector<char>ch;vector<int>need;// 压缩目标串 Afor(inti=0;i<n;){intj=i;while(j<n&&A[j]==A[i])j++;ch.push_back(A[i]);need.push_back(j-i);i=j;}intk=ch.size();longlongans=0;// 枚举子串左端点for(intl=0;l<m;l++){intcnt=0;intindx=0;// 枚举子串右端点for(intr=l;r<m;r++){if(S[r]==ch[indx]){cnt++;}else{// 上一段长度不够，失败if(cnt<need[indx])break;// 进入下一段indx++;// 段数超过目标串，失败if(indx>=k)break;// 新段字符不匹配，失败if(S[r]!=ch[indx])break;// 当前字符是新段的第一个字符cnt=1;}// 已经匹配到最后一段，并且长度够if(indx==k-1&&cnt>=need[indx]){ans++;}}}cout<<ans<<"\n";return0;}复杂度
时间复杂度：O(m^2) 空间复杂度：O(n)题目二：数据传输网络最小时延
题目描述
有N个数据交换节点，编号为0到N - 1。数据包从节点0开始，按编号顺序依次经过每个节点，到达节点N - 1。
每个节点i默认产生delay[i]单位处理时延。
如果在节点i配置优先转发模式，它会影响本节点和后续win_size[i]个节点。受影响节点j的处理时延会减少opt_delay[i]，如果多个节点同时影响j，则可以重复减少，但最终时延不能小于0。
最多选择K个节点配置优先转发模式，求最小总处理时延。
约束：
3 <= N <= 50 0 <= K <= 10 0 <= win_size[i] <= 3样例 1
输入：
3 1 50 40 30 3 0 1 0 50 10输出：
80解释：
选择节点1最优，节点1的处理时延从40降到0。
总时延：
50 + 0 + 30 = 80样例 2
输入：
5 2 10 20 30 40 50 1 0 1 3 2 15 20 0 30 35输出：
65解释：
选择节点0和节点3最优。
节点0影响节点0和1：
节点 0: 10 -> 0 节点 1: 20 -> 5节点3影响节点3和4：
节点 3: 40 -> 10 节点 4: 50 -> 20总时延：
0 + 5 + 30 + 10 + 20 = 65题解思路
不能贪心，因为一个节点的收益会受到其他节点是否被选的影响。
关键限制是：
win_size[i] <= 3所以处理节点i时，最多只有这几个节点能影响它：
i - 3, i - 2, i - 1, i因此可以用状态压缩 DP，只记录前面 3 个节点是否被选。
定义：
dp[i][used][mask]表示：
已经处理完前 i 个节点，也就是 0 ~ i - 1 已经选择了 used 个节点 最近 3 个节点的选择状态为 mask 此时的最小总时延其中mask的含义：
bit0：i - 1 是否被选 bit1：i - 2 是否被选 bit2：i - 3 是否被选每次处理节点i，枚举当前节点选或不选。
代码：三维 DP 写法
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,K;cin>>N>>K;vector<longlong>delay(N),opt_delay(N);vector<int>win_size(N);for(inti=0;i<N;i++)cin>>delay[i];for(inti=0;i<N;i++)cin>>win_size[i];for(inti=0;i<N;i++)cin>>opt_delay[i];constlonglongINF=4e18;// dp[i][used][mask]vector<vector<vector<longlong>>>dp(N+1,vector<vector<longlong>>(K+1,vector<longlong>(8,INF)));dp[0][0][0]=0;for(inti=0;i<N;i++){for(intused=0;used<=K;used++){for(intmask=0;mask<8;mask++){if(dp[i][used][mask]==INF)continue;// take = 0 表示不选 i// take = 1 表示选择 ifor(inttake=0;take<=1;take++){if(used+take>K)continue;longlongreduce=0;// 当前节点 i 被选，会影响自己if(take){reduce+=opt_delay[i];}// 检查 i - 1, i - 2, i - 3 是否能影响 ifor(intd=1;d<=3;d++){intp=i-d;if(p<0)continue;// mask 第 d - 1 位表示 i - d 是否被选if((mask>>(d-1))&1){if(p+win_size[p]>=i){reduce+=opt_delay[p];}}}longlongcurDelay=delay[i]-reduce;if(curDelay<0)curDelay=0;// 下一轮处理 i + 1// bit0 表示 i 是否被选// bit1 表示 i - 1 是否被选// bit2 表示 i - 2 是否被选intnewMask=((mask<<1)&7)|take;dp[i+1][used+take][newMask]=min(dp[i+1][used+take][newMask],dp[i][used][mask]+curDelay);}}}}longlongans=INF;// 最多选 K 个，所以 used 可以小于等于 Kfor(intused=0;used<=K;used++){for(intmask=0;mask<8;mask++){ans=min(ans,dp[N][used][mask]);}}cout<<ans<<"\n";return0;}复杂度
时间复杂度：O(N * K * 8 * 2 * 3) 空间复杂度：O(N * K * 8)因为N <= 50，K <= 10，状态数量很小，可以轻松通过。