Codeforces 1296E2. String Coloring (hard version)

这道题和HDU1257一模一样，一开始窝都用贪心直接解，没法理解为什么求一个最长下降序列，直到看了巨巨的题解，先给出一个定理，Dilworth's theorem,离散学不好，补题两行泪，该定理是说，对于任意的偏序集，其最长反链的长度与能分解的最少的链数(chain decomposition)相等，反链(anti-chain)是指该链内任意元素不可比(incomparable),链(chain)则是都可比，回到这一题，要求的是递增链的最小数目，即递增链最小分解数，转换成求其递减链的最长长度即可，转换成了dp问题，先上贪心代码

const int maxm = 2e5+;

int colors[maxm], cache[maxm];

void run_case() {

    int n;

    string str;

    cin >> n >> str;

    int res = ;

    for(int i = ; i < n; ++i) {

        int c = str[i] - 'a';

        bool neednew = false;

        for(int j = ; j <= res; ++j) {

            if(colors[j] <= c) {

                colors[j] = c, cache[i] = j; break;

            }

            if(j == res) neednew = true;

        }

        if(neednew) {

            colors[++res] = c, cache[i] = res;

        }

    }

    cout << res << "\n";

    for(int i = ; i < n; ++i) {

        cout << cache[i] << " ";

    }

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    //cout.flush();

    return ;

}

贪心

设dp[i]表示以i结尾的最长的decrease链，则状态转移为:

1.若str[i] < str[i-1], dp[i]=dp[i-1]+1

2.若str[i] >= str[i-1] dp[i]=1

但是，这个状态与m段最大子段和一样，i的上一个increase字符不一定是i-1，例如bca,dp[a]为2而不为1，我们就模仿m段最大子段和，设maxdp[i]为字母i结尾的最长的decrease链长度，

则dp[i] = max(1,maxdp[pre]+1), pre表示比i大的字母，然后再用dp更新maxdp即可，maxdp[str[i]] = max(maxdp[str[i]], dp[i])，那么，我们如何恢复答案呢，看dp数组更新时，若dp[i]大于了maxdp[pre]，因为我们要求的是increase链，则str[i]无法接在pre(比str[i]大的字母)后面，就要用一个新的颜色，即更新了dp[i]，所以dp[i]就是答案

void run_case() {

    int n;

    string str;

    cin >> n >> str;

    vector<int> maxdp();

    vector<int> dp(n, );

    for(int i = ; i < n; ++i) {

        for(int c = ; c > str[i]-'a'; --c) {

            dp[i] = max(dp[i], maxdp[c]+);

        }

        maxdp[str[i]-'a'] = max(maxdp[str[i]-'a'], dp[i]);

    }

    cout << *max_element(maxdp.begin(), maxdp.end()) << "\n";

    for(int i = ; i < n; ++i)

        cout << dp[i] << " ";

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    //cout.flush();

    return ;

}

巴特西

Codeforces 1296E2. String Coloring (hard version)

最新文章

热门文章