思路:
- 条件:标定字符串,保证其中有USTC且按顺序;
- 问题:求将之合并最短代价;
- 显然考虑中点,容易证明中点最小,min(ans) = x[4] - x[1] + x[3] - x[2] - 2 - 2;
- 直接计算输出即可;
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
char s[MAXN];
char s1[6]={'0','U','S','T','C'};
int x[6];
int main()
{scanf("%s",s+1);int n=strlen(s+1),cnt=1;for(int i=1;i<=n;i++){if(s[i]==s1[cnt]){x[cnt]=i;cnt++;}}int ans=0;ans += x[4] - x[1] - 1;ans += x[3] - x[2] - 1;ans -= 2;cout<<ans<<endl;return 0;
}