《Balance》解题报告.pdfVIP

《Balance》解题报告 中山纪念中学 梁健楠 【题源】 本题来自CODEFORCES 17C—— 《Balance》。 【前言】 本题是一道DP题，巧妙地设计状态以及转移方法。主要考验同学的思维能力。 【题目大意】 给定一串长度为n 150，只包含abc 三种字符的字符串s，能对其进行两种 操作： 1，选相邻的两个字符，将后面的字符变成前面的字符，如：ab 变成aa； 2，选相邻的两个字符，将前面的字符变成后面的字符，如：ab 变成bb。 记|a|，|b|，|c|分别为字符串s 中a，b，c 出现的个数。定义平衡字符串 必须同时满足-1 |a|- |b| 1，-1 |a|- |c| 1，-1 |b|- |c| 1。 问：字符串s 通过若干次操作后，能变换成多少个不同的平衡字符串。 样例输入： 样例输出： Case 1: Case 1: 4 7 abca Case 2: Case 2: 3 4 Case 3: abbc 1 Case 3: 2 ab 【问题分析】 首先忽略对新字符串|a|,|b|,|c|限制，思考原字符串s 与转换后新字符串 s1 的关系。 原串s 中某一位置上的字符能通过操作将新串s1 中任意位置更新为该字符。 定义序列g(i)表示新串s1 中第i位字符是从原串s 中第g(i)位字符更新过来的。 可得性质：对于任意i j，有g(i) g(j)。也就是说，序列g 是不下降序列。 而同一个新字符串s1可能对应很多种不同的g序列，现在规定两个限制：1） 新串s1 中相邻两个字符相同的位置i 和i+1,限定g(i)=g(i+1)；2）新串s1 中 相邻两个字符不相同的位置 i 和 i+1，限定原串s 中第g(i)至g(i+1)位之间不 存在与第 g(i+1)位字符相同的字符(即g(i+1)是 g(i)位后不同字符出现的最先 位置)，这样能使得一个新字符串s1 对以一种g 序列。 根据上述限制，设计DP，f[i][na][nb][nc]表示新字符串长度为na+nb+nc， 其中a,b,c 字符分别出现na,nb,nc 次，g(na+nb+nc)=i 的字符串数。 先预处理出next 数组，next[i][ch]表示原字符串第 i 位后字符ch 最先出 现的位置。 转移时,枚举下一位字符，并根据规定的限制更新 i(要注意状态枚举的顺 序)。 假如统计出所有新字符串，那么 na,nb,nc 最大能达到 n，算法的时间复杂 度和空间复杂度都会达到O(n^4)。 考虑用对新字符串|a|,|b|,|c|的限制来优化，要保证-1 |a|- |b| 1， -1 |a|- |c| 1，-1 |b|- |c| 1，那么|a|,|b|,|c|最大只有(n+2)/3。这样 na,nb,nc 也只需枚举到(n+2)/3。 最后统计所有满足na+nb+nc=n 且-1 na-nb 1，-1 na-nc 1，-1 nb-nc 1 的状态的和。 至此，算法的时间复杂度为O(n* （n/3）^3)，能在规定时间内求得解。 【程序实现(pascal)】 const maxp var N,M,i,a,b,c,ans:longint; ch:array[0..155]of char; f:array[0..155,0..55,0..55,0..55]of longint; next:array[0..155,0..3]of longint; begin readln(N); for i:=1 to N do read(ch[i]); readln;