本文主要是介绍2020 Southeast USA Regional 部分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A-Ant Typing
一开始我就想到用枚举，但是估算错了枚举的规模，算成了9^9，觉得枚举规模过大就放弃了。实际上只有9!种情况，大概三十多万种，也就是A(9,9)。stl中提供了一个生成字典序的函数next_permutation()，可以用这个函数来简化代码量。对于计算结果，无需每次遍历输入的字符串，只要记录从一个数字到另一个数字的次数即可，也就是cnt[i][j]表示从i到j的次数，然后根据生成的字典序列计算就好。
#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);int cnt[10][10] = {0}; //cnt[i][j]记录蚂蚁从i+1到j+1的次数int ans = 100000000, temp;string str;vector<int> perm(10,0);cin >> str;for (int i = 1; i < str.size(); i++)//统计cnt{cnt[str[i - 1] - '0'][str[i] - '0']++;}for (int i = 1; i <= 9; i++) //perm[i]表示数字i在第perm[i]个位置{perm[i]=i;}do{temp = perm[str[0]-'0']-1;//蚂蚁一开始位于最左边，加上从最左边到第一个数字的距离for (int i = 1; i <= 9; i++){for (int j = i + 1; j <= 9; j++){temp += (cnt[i][j] + cnt[j][i]) * abs(perm[i]-perm[j]);}}if (temp < ans){ans = temp;}} while (next_permutation(perm.begin()+1, perm.end()));ans += str.size();//每个位置都要停留一秒来敲击键盘cout << ans ;return 0;
}
这篇关于2020 Southeast USA Regional 部分题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
