p1125 [noip2008 提高组] 笨小猴
时间: 2023-04-23 12:06:22 浏览: 112
题目描述:
笨小猴在玩耍,它有一个长度为 n 的字符串 s。它想把这个字符串切成若干个非空的子串,使得每个子串都是回文串。它最少需要切几刀?
输入格式:
输入共一行,为一个长度为 n 的字符串 s。
输出格式:
输出共一行,为一个整数,表示最少需要切的刀数。
数据范围:
1≤n≤500
输入样例:
aab
输出样例:
1
算法1
(动态规划) $O(n^2)$
1.状态表示
dp[i]表示前i个字符最少可以分成几个回文串
2.状态转移
dp[i] = min(dp[j] + 1) (j < i && j + 1 ~ i是回文串)
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(中心扩展) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
P1563 [NOIP2016 提高组] 玩具谜题
P1563 [NOIP2016 提高组 玩具谜题是一个关于玩具人隐藏眼镜的谜题。在这个谜题中,Xiaonan拥有一套可爱的玩具人,每个玩具人都有不同的职业。有一天,这些玩具人把Xiaonan的眼镜藏起来了。Xiaonan发现玩具人围成了一个圆圈,一些面向圆圈内部,一些面向圆圈外部。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [P1563 [NOIP2016 提高组] 玩具谜题(找规律,心要细,数学思维)](https://blog.csdn.net/m0_57071296/article/details/119763478)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
p1011 [noip1998 提高组] 车站
题目描述:
有一个车站,有n个人要上车,但是车只有m个座位,所以只有前m个人能够上车,后面的人只能等下一班车。现在有k辆车,每辆车的座位数也是m个,问最少需要多少时间才能让所有人都上车?
输入格式:
输入共k+1行,第一行包含三个整数n,m,k,分别表示总人数,每辆车的座位数,以及车的数量。
接下来k行,每行包含m个整数,表示每辆车上的人的编号,编号从1开始。
输出格式:
输出一个整数,表示最少需要的时间。
输入样例:
10 3 3
1 2 3
4 5 6
7 8 9
10
输出样例:
4
算法1
(贪心) $O(n)$
每辆车都坐满,这样可以保证最少的车次数。
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码