CODE FESTIVAL 2017 qual B D 101 to 010(dp)

除非人品好，能碰巧想到思路，否则基本是做不出来dp的，除了那几个经典的dp模型。。
看了几个前几名的代码，还是t神的代码比较清晰。膜tourist
代码的思路和题解思路基本一致。。。。。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1234567;

char s[MAXN];

int f[MAXN];

int nxt[MAXN],prv[MAXN];

int main()

{

    int n;

    scanf("%d", &n);

    scanf("%s", s);

    memset(f,0,sizeof(f));

    nxt[n] = n;

    //记录以当前位置开始，向后数，第一个0的位置

    for(int i = n-1; i >= 0; --i)

    {

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

            nxt[i] = i;

        else

            nxt[i] = nxt[i+1];

    }

    //记录以当前位置开始，向前数，第一个0的位置

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

    {

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

            prv[i] = i;

        else

            prv[i] = (i==0?-1:prv[i-1]);

    }

    //两个部分分别更新当前位置和向后更新

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

    {

        //更新11111101...这种形式的子串

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

        {

            int j = prv[i-3];

            f[i] = max(f[i],f[j+1]+(i-j-3));

            if(j != i-4)

                f[i] = max(f[i],f[j+2]+(i-j-4));

        }

        if(i == n)

            break;

        //更新11111101....这种形式的子串

        if(i+3 <= n && s[i] == '1' && s[i+1] == '0' && s[i+2] == '1')

        {

            int j = nxt[i+2];

            f[j] = max(f[j],f[i]+(j-i-2));

            if(j != i+3)

                f[j-1] = max(f[j-1],f[i]+(j-i-3));

        }

        f[i+1] = max(f[i+1],f[i]);

    }

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

    return 0;

}

巴特西

CODE FESTIVAL 2017 qual B D 101 to 010(dp)

最新文章

热门文章