【C++板块提升计划】梦想护卫舰 第17关 旋转与回文【答题有奖】
本帖最后由 zhangjinxuan 于 2023-1-30 14:00 编辑上一关：阶乘之和
梦想护卫舰 第17关 旋转与回文
好了，你们通过了宝箱守护者的挑战，可以打开装有 1e5 的鱼币宝箱了~（好耶！）
但是（我就知道）
你们发现宝箱需要密码，宝箱上面只有一个长度为 N 的字符串 S（所以到底要干什么）
因为你成功答对了宝箱守护者的题目，所以他们给了你一些提示：
我们先定义 Si 为 S 从左往右的第 i 个字符（有点废话）
你可以按任意顺序执行下列操作 0 次或很多次：
[*]花费 A 的体力，将 S1 添加到 Sn 的后面，并把 S1 删除，换句话说，把原本 S 的 S1，S2, …… Sn 变成 S2，S3, …… Sn，S1
[*]花费 B 的体力，更改 S 的其中一个字符，新字符必须是小写字母
你需要把 S 变成回文串
你至少花费的体力，就是打开宝箱的密码
数据范围
1 <= n <= 5000
1 <= A, B <= 1e9
Si (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，题解个人原创
static/image/hrline/1.gif
答案与解析
请认真思考再查看答案！
**** Hidden Message *****
最佳题解排行榜
(排行未确定，大家还有上榜机会！）
|第一名|第二名|第三名
名字|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. 因为额度原因，部分鱼油可能下一天才能奖励。
static/image/hrline/1.gif
**** Hidden Message *****
下一关：解密（2)
创作不易，如果你喜欢，别忘了评分、顶{:10_281:}
本关满意度调查 本帖最后由 ExiaGN001 于 2023-1-29 08:28 编辑
已测ACcepted 17/17（含2sample）
评测记录可查:
https://www.luogu.com.cn/record/100716963
https://atcoder.jp/contests/abc286/submissions/38436035
//洛谷/ATCoder
//AT_abc286_c
//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;
char s2;
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=s;
for(int j=n-i+1;j<=n;j++)s2=s;
if(n%2==0)
for(int l=n/2,r=n/2+1;l>=1&&r<=n;l--,r++)
{
if(s2!=s2)tmpans+=b;
}
else
for(int l=n/2,r=n/2+2;l>=1&&r<=n;l--,r++)
{
if(s2!=s2)tmpans+=b;
}
ans=min(ans,tmpans);
}
cout<<ans;
return 0;
}
本帖最后由 ExiaGN001 于 2023-1-29 07:53 编辑
给大家一些题意补充。首先捉虫。
1.在操作之后，S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下。 ExiaGN001 发表于 2023-1-29 07:39
给大家一些题意补充。首先捉虫。
1.在操作之后，S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下 ...
不好意思，1忘了写上去{:10_282:} ExiaGN001 发表于 2023-1-29 08:26
已测ACcepted 17/17（含2sample）
评测记录可查:
https://www.luogu.com.cn/record/100716963
太强了 {:10_285:}
页:
[1]