[已解决]【C++板块提升计划】梦想护卫舰 第17关 旋转与回文【答题有奖】

zhangjinxuan

上一关：阶乘之和

梦想护卫舰 第17关 旋转与回文

好了，你们通过了宝箱守护者的挑战，可以打开装有 1e5 的鱼币宝箱了~（好耶！）

但是（我就知道）

你们发现宝箱需要密码，宝箱上面只有一个长度为 N 的字符串 S（所以到底要干什么）

因为你成功答对了宝箱守护者的题目，所以他们给了你一些提示：

我们先定义 S_i 为 S 从左往右的第 i 个字符（有点废话）

你可以按任意顺序执行下列操作 0 次或很多次：

• 花费 A 的体力，将 S₁ 添加到 S_n 的后面，并把 S₁ 删除，换句话说，把原本 S 的 S₁，S₂, …… S_n 变成 S₂，S₃, …… S_n，S₁
• 花费 B 的体力，更改 S 的其中一个字符，新字符必须是小写字母
  

你需要把 S 变成回文串

你至少花费的体力，就是打开宝箱的密码

数据范围
1 <= n <= 5000
1 <= A, B <= 1e9
S_i (1 <= i <= n) 是小写字母
除了 S，所有数据都是整数

输入格式

所有输入参照以下格式：

N A B
S

输出格式

输出一个整数表示答案

输入样例1

5 1 2
rrefa

输出样例1

3

样例解释1
（请自行翻译，宝箱守护者是歪果仁）

First, pay 2 yen to perform the operation of the second kind once:
let i=5 to replace S 5 with e. S is now "rrefe".
Then, pay 1 yen to perform the operation of the first kind once.
S is now "refer", which is a palindrome.
Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

输入样例2

8 1000000000 1000000000
bcdfcgaa

输入样例2

4000000000

样例解释2

Note that the answer may not fit into a 32-bit integer type.

注意：本题非原创，改编于 ABC 286 C，题解个人原创

                               
登录/注册后可看大图

答案与解析
请认真思考再查看答案！

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳题解排行榜
(排行未确定，大家还有上榜机会！）

	第一名	第二名	第三名
名字	ExiaGN001	等待着聪明的编程王者~
链接	戳我
语言	C++
效率	34ms
代码得分	100
综合得分	100
奖励	5鱼币5荣誉+“最佳答案”	3鱼币3荣誉	2鱼币2荣誉

/*综合评分会参照运行时间（代码效率），代码长度，代码可读性，解题思路，代码得分等来进行评分*/


答题规则
1. 不能抄题解，否则无奖励，可能还会扣分;
2. 爆零的代码，视为普通回帖，不会奖励；
3. 语言任意。
4. 当您遇到问题时，您可以回贴提问，我会为您解答

奖励规则
1. 奖励3天后统一发，3天内发布的题解才有效；
2. 提供完整题解，但没有上排行榜，奖励1鱼币+1荣誉；
3. 高于1鱼币1荣誉的奖励，仅给排行榜上的鱼油（因为经济原因，请谅解）；
4. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

游客，如果您要查看本帖隐藏内容请回复

[/hide]

下一关：解密（2)

创作不易，如果你喜欢，别忘了评分、顶


本关满意度调查

最佳答案

月排行榜 / 总排行榜

ExiaGN001

2023-1-29 08:26:31

已测ACcepted 17/17（含2sample）
评测记录可查:
https://www.luogu.com.cn/record/100716963

https://atcoder.jp/contests/abc286/submissions/38436035

//洛谷/ATCoder
//AT_abc286_c [ABC286C]
//Rotate and Palindrome

#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        long long n,a,b;
        unsigned long long ans,tmpans;
        char s[11451];
        char s2[11451];

        scanf("%lld%lld%lld",&n,&a,&b);
        scanf("%s",s+1);

        ans=1000000000000000000;
        tmpans=0;

        for(int i=0;i<=n;i++)
        {
                tmpans=a*i;

                for(int j=1;j<=n-i;j++)s2[j]=s[j+i];
                for(int j=n-i+1;j<=n;j++)s2[j]=s[j-n+i];

                if(n%2==0)
                        for(int l=n/2,r=n/2+1;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                else
                        for(int l=n/2,r=n/2+2;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                ans=min(ans,tmpans);
        }
        cout<<ans;
        return 0;
}

跳转到最佳答案楼层

ExiaGN001

已测ACcepted 17/17（含2sample）
评测记录可查:
https://www.luogu.com.cn/record/100716963

https://atcoder.jp/contests/abc286/submissions/38436035

//洛谷/ATCoder
//AT_abc286_c [ABC286C]
//Rotate and Palindrome

#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        long long n,a,b;
        unsigned long long ans,tmpans;
        char s[11451];
        char s2[11451];

        scanf("%lld%lld%lld",&n,&a,&b);
        scanf("%s",s+1);

        ans=1000000000000000000;
        tmpans=0;

        for(int i=0;i<=n;i++)
        {
                tmpans=a*i;

                for(int j=1;j<=n-i;j++)s2[j]=s[j+i];
                for(int j=n-i+1;j<=n;j++)s2[j]=s[j-n+i];

                if(n%2==0)
                        for(int l=n/2,r=n/2+1;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                else
                        for(int l=n/2,r=n/2+2;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                ans=min(ans,tmpans);
        }
        cout<<ans;
        return 0;
}

ExiaGN001

给大家一些题意补充。首先捉虫。
1.在操作之后，S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下。

zhangjinxuan

ExiaGN001 发表于 2023-1-29 07:39
给大家一些题意补充。首先捉虫。
1.在操作之后，S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下 ...

不好意思，1忘了写上去

hziyan

ExiaGN001 发表于 2023-1-29 08:26
已测ACcepted 17/17（含2sample）
评测记录可查:
https://www.luogu.com.cn/record/100716963

太强了

元豪