A4731 | Yuilice的偶数回文串
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
一个偶回文串是一个正着读和倒着读都一样的，长度为偶数的字符串。如果一个串可以被若干个偶回文串拼接而来，就认为这个字符串是美丽的。
Yuilice给你一个$01$串$t$，你需要进行若干次反转操作（$0$变$1$或者$1$变$0$），反转第$i$位需要花费$w_i$的代价。请你使用最小代价把$t$变成一个美丽的字符串，请输出最小总代价。数据保证可以把$t$变成美丽的字符串。
Yuilice给你一个$01$串$t$，你需要进行若干次反转操作（$0$变$1$或者$1$变$0$），反转第$i$位需要花费$w_i$的代价。请你使用最小代价把$t$变成一个美丽的字符串，请输出最小总代价。数据保证可以把$t$变成美丽的字符串。
输入格式
第一行一个整数$n$表示字符串$t$的长度。
第二行一个字符串$t$。
第三行包含$n$个由空格隔开的整数$w_1,w_2,...w_n$。
第二行一个字符串$t$。
第三行包含$n$个由空格隔开的整数$w_1,w_2,...w_n$。
输出格式
输出一个一个非负整数表示最小总代价。
输入输出样例
输入 #1
8 00101011 8 7 6 5 4 3 2 1
输出 #1
5
样例解释
可以修改第$6$位和第$7$位，使得字符串变为$00101101$，它是由两个偶回文串拼接而来的：$00+101101$。
数据规模与约定
对于$10\%$的数据，保证$n\leq 6$。
对于其他$20\%$的数据，保证$n\leq 40$。
对于其他$30\%$的数据，保证$n\leq 300$。
对于所有数据，保证$1\leq n \leq 2000$，$0\leq w_i \leq 10^5$，保证$n$是一个偶数。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？