NC224878. ReMorse
描述
Morse code is an assignment of sequences of dot and dash symbols to alphabet characters. You are to reassign the sequences of Morse code so that it yields the shortest total length to a given message, and return that total length.
A dot symbol has length 1. A dash symbol has length 3. The gap between symbols within a character encoding has length 1. The gap between character encodings has length 3. Spaces, punctuation, and alphabetic case are ignored, so the text
The quick brown dog jumps over the lazy fox.
is encoded as though it were
THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX
For instance, for the input ICPC, the answer is 17. Encode the Cs with a single dot, the I with a dash, and the P with two dots, for an encoding of
− ∙ ∙∙ ∙
which has length (3) + 3 + (1) + 3 + (1 + 1 + 1) + 3 + (1) = 17.
输入描述
The single line of input consists of a string s (1 ≤ |s| ≤ 32000) of upper-case or lower-case letters, spaces, commas, periods, exclamation points, and/or question marks. Everything but the letters should be ignored. The line will contain at least one letter.
输出描述
Output a single integer, which is the length of 𝒔 when encoded with an optimal reassignment of the sequences of Morse code.
示例1
输入:
ICPC
输出:
17
示例2
输入:
A
输出:
1
示例3
输入:
The quick brown dog jumps over the lazy fox.
输出:
335
C++ 解法, 执行用时: 5ms, 内存消耗: 388K, 提交时间: 2021-08-31 19:37:15
#include<algorithm>
#include<cstdio>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int N=32005,sum[6]={1,3,6,11,19,32};
int ans=-3,a[26];
int main()
{
for (char ch=getchar();ch!='\n';ch=getchar())
{
if ('A'<=ch&&ch<='Z') a[ch-'A']++,ans+=3;
if ('a'<=ch&&ch<='z') a[ch-'a']++,ans+=3;
}
sort(a,a+26);reverse(a,a+26);
int _=0;rep(i,0,25) if (a[i])
{
if (i>=sum[_]) _++;
ans+=a[i]*(2*_+1);
}
printf("%d\n",ans);return 0;
}