当前位置：网站首页>托米的咒语

托米的咒语

2022-08-10 11:12:00 【51CTO】

题目描述

托米没有完成上一个任务，准备施展黑魔法推倒 1317

黑魔法咒语被描述为一个长为 n 的，仅包含小写英文字母 'a'...'i' 的字符串，在托米所在的星球，魔法造成的每次有效伤害都是来自他的一个子序列，对于每一个 'a'... 'i' 的排列(共 9! 种)，若作为咒语的子序列出现, 就会造成 1 的伤害

而咒语的总伤害为所有 'a'... 'i' 的排列造成的伤害值之和，托米能打出多少点的伤害，是否能击败 1317 呢？

输入描述:

一行输入一个字符串 s

输出描述:

一行输出一个数，表示伤害值

示例1

输入

aabcdefghi

输出

备注:

|s| ≤ 3000

这个是题解的做法，dp[i][j]表示第i位右边最近的 j 的位置。找全排列的时候方便寻找。

代码：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       #define ll long long
       
       const 
       
       int 
       
       maxn
       
       =
       
       3000
       
       +
       
       10;
       
       const 
       
       int 
       
       INF
       
       =
       
       0x3f3f3f3f;
       
       char 
       
       p[
       
       10]
       
       =
       
       "abcdefghi";
       
       char 
       
       s[
       
       maxn];
       
       int 
       
       dp[
       
       maxn][
       
       10];
       
       int 
       
       num[
       
       10];
       
       int 
       
       main()
       
{
       
       scanf(
       
       "%s",
       
       s
       
       +
       
       1);
       
       s[
       
       0]
       
       =
       
       ' ';
       
       int 
       
       l
       
       =
       
       strlen(
       
       s);
       
       for(
       
       int 
       
       i
       
       =
       
       l
       
       -
       
       1;
       
       i
       
       >=
       
       0;
       
       i
       
       --)
       
    {
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       9;
       
       j
       
       ++)
       
        {
       
       dp[
       
       i][
       
       j]
       
       =
       
       num[
       
       j];
       
        }
       
       num[
       
       s[
       
       i]
       
       -
       
       'a']
       
       =
       
       i;
       
    }
       
       ll 
       
       ans
       
       =
       
       0;
       
       do{
       
       int 
       
       k
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       9;
       
       i
       
       ++)
       
        {
       
       k
       
       =
       
       dp[
       
       k][
       
       p[
       
       i]
       
       -
       
       'a'];
       
       if(
       
       !
       
       k)
       
            {
       
       ans
       
       --;
       
       break;
       
            }
       
        }
       
       ans
       
       ++;
       
    }
       
       while(
       
       next_permutation(
       
       p,
       
       p
       
       +
       
       9));
       
       printf(
       
       "%lld\n",
       
       ans);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.