A题枚举即可。
怎么想呢?枚举“吸引子”即可,即所有颜色与“吸引子”颜色相同的巧克力都要往“吸引子”所在位置靠拢。
复杂度为

/*5ms*/

const int mx = 55;

p2 dis[mx];

class ColorfulChocolates
{
    public:
        int maximumSpread(string s, int ms)
        {
            int ans = 0, i, j, n = s.size(), tmp, cnt;
            For(i, n)
            {
                mem(dis, 0);
                For(j, n) dis[j].second = j;
                rFor(j, i - 1) dis[j].first = dis[j + 1].first + (s[j] != s[i]);
                Forr(j, i + 1, n) dis[j].first = dis[j - 1].first + (s[j] != s[i]);
                sort(dis, dis + n);
                tmp = ms, cnt = 0;
                For(j, n)
                {
                    if (s[dis[j].second] != s[i]) continue;
                    if (tmp - dis[j].first < 0) break;
                    tmp -= dis[j].first, ++cnt;
                }
                ans = max(ans, cnt);
            }
            return ans;
        }
};

Comments

comments powered by Disqus