CF1011A Stages

    • 56通过
    • 83提交
  • 题目来源 CodeForces 1011A
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    定义一个长度为$n$的字符串$s$的价值为$$\sum_{i=1}^{n}(s[i]-'a'+1)$$定义一个长度为$n$的字符串$s$是优秀的,当且仅当$$\forall x \in [1,n-1] (s[x]-'a')<(s[x+1]-'a'-1)$$现在给出一个长度为$n$字符串$t$,求在从$t$中选$k$个字符所能组成的所有优秀的字符串中价值最低的的价值,如果不能构造出优秀的序列,输出$-1$。

    输入输出格式

    输入格式

    第一行两个整数,$n$和$k(1\le k \le n \le 50)$;

    第二行一个字符串$t$,保证$t$只由小写字母组成。

    输出格式

    一个整数,即最低价值。

    题目描述

    Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages.

    There are $ n $ stages available. The rocket must contain exactly $ k $ of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter 'c' can't go letters 'a', 'b', 'c' and 'd', but can go letters 'e', 'f', ..., 'z'.

    For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage 'a 'weighs one ton,' b 'weighs two tons, and' z' — $ 26 $ tons.

    Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.

    输入输出格式

    输入格式:

    The first line of input contains two integers — $ n $ and $ k $ ( $ 1 \le k \le n \le 50 $ ) – the number of available stages and the number of stages to use in the rocket.

    The second line contains string $ s $ , which consists of exactly $ n $ lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.

    输出格式:

    Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.

    输入输出样例

    输入样例#1: 复制
    5 3
    xyabd
    
    输出样例#1: 复制
    29
    输入样例#2: 复制
    7 4
    problem
    
    输出样例#2: 复制
    34
    输入样例#3: 复制
    2 2
    ab
    
    输出样例#3: 复制
    -1
    输入样例#4: 复制
    12 1
    abaabbaaabbb
    
    输出样例#4: 复制
    1

    说明

    In the first example, the following rockets satisfy the condition:

    • "adx" (weight is $ 1+4+24=29 $ );
    • "ady" (weight is $ 1+4+25=30 $ );
    • "bdx" (weight is $ 2+4+24=30 $ );
    • "bdy" (weight is $ 2+4+25=31 $ ).

    Rocket "adx" has the minimal weight, so the answer is $ 29 $ .

    In the second example, target rocket is "belo". Its weight is $ 2+5+12+15=34 $ .

    In the third example, $ n=k=2 $ , so the rocket must have both stages: 'a' and 'b'. This rocket doesn't satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。