题目链接

题意

对于一个\(01\)串，如果其中存在子串\(101\)，则可以将它变成\(010\). 问最多能进行多少次这样的操作。

思路

官方题解

转化

倒过来考虑。

考虑，最终得到的串中的\('1'\)的来源

1-1

|

-101--101

	|

	--1011----1011

	|     |

	|     ----10111--------……

	--1101----1101

		  |

		  ----11101--------……

所以，最终的\('1'\)对应着最初的串中的

\(1\)
\(111...11101\)
\(10111...111\)

于是问题转化为：

有两种好串，一种是\(111...11101\)(\(k\)个\(1\),\(1\)个\(0\),\(1\)个\(1\))，价值为\(k\)；另一种是\(10111...111\)(\(1\)个\(1\),\(1\)个\(0\),\(k\)个\(1\))，价值为\(k\). 现在要从\(s\)中选择不重叠的好串使得价值最大，问最大价值是多少。

DP

乍一看是个\(O(n^2)\)的\(dp\)，事实上可以做到\(O(n)\).

对于每个\(1\)记录其前面与它最接近的\(0\)的位置，就可以预处理出所有的好串的位置。在好串间进行转移即可。

Code

参考:

http://code-festival-2017-qualb.contest.atcoder.jp/submissions/1666040

#include <bits/stdc++.h>

#define maxn 500010

using namespace std;

char s[maxn];

int a[maxn], dp[maxn];

int main() {

    int n;

    scanf("%d%s", &n, s+1);

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

        if (s[i] == '0') a[i] = i;

        else a[i] = a[i-1];

    }

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

        dp[i] = dp[i-1];

        if (s[i] == '1') {

            if (s[i-1] == '0' && s[i-2] == '1') {

                dp[i] = max(dp[i], dp[a[i-2]]+ (i-2) - a[i-2]);

                dp[i] = max(dp[i], dp[a[i-2]+1] + (i-2) - (a[i-2]+1));

            }

            else if (a[i]>1 && s[a[i]-1] == '1') dp[i] = max(dp[i], dp[a[i]-2] + i - a[i]);

        }

    }

    printf("%d\n", dp[n]);

    return 0;

}

巴特西

Atcoder CODE FESTIVAL 2017 qual B D - 101 to 010 dp

题目链接

题意

思路

官方题解

转化

DP

Code

最新文章

热门文章