codeforces 704B - Ant Man [想法题]

题目链接:http://codeforces.com/problemset/problem/704/B

--------------------------------------------------------------------------------

比赛时最远也就猜到了拆公式,算贡献这一步然后就$GG$了

结束后问了$Randolph87$ 他给了一个"括号匹配"的思路

感觉这个思路比官方题解更可做然后我就按照这个思路开始思考

对于非起点非终点外的所有点有这四种情况

左入左出左入右出右入左出右入右出

每当加入一个新的点

如果它是右入右出则当前区间的入度 $+1$ 出度 $+1$

如果是左入左出则当前区间的入度 $-1$ 出度 $-1$

另外两种情况则是入度出度都不改变

(此处度数是对于整个区间讲的或者说这个区间对应的有向图还需要增加$x$个入度和$y$个出度才能构成一个环)

假设题目不限定起点终点只要求一个回路那么对于所有的点都这样做

并且保证中间状态中入度出度都为正数最终状态入度出度都为$0$即可

然而题目是有起点和终点限制的一条路径

因此我们可以强行连一条从终点出从起点入的代价为$0$的边

按照这个思路做下去一部分人会$WA5$

原因是在实现的时候有可能只是限定了终点有一条方向向着起点的边

于是中间还可能混入其他的点并没有保证终点和起点的直接连接

为了满足这个要求我们可以在扫描到起点和终点之间的点的时候

强行使得入度$-1(s < e$时$)$ / 出度 $-1(s > e$时$)$

这样就可以把这一部分完美地解决了

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = ;

long long f[N][N];

bool valid[N][N];

int x[N], a[N], b[N], c[N], d[N];

int n, s, e;

void update(long long &x, long long y, bool &z)

{

    if(!z)

    {

        z = ;

        x = y;

        return;

    }

    x = min(x, y);

}

int main()

{

    scanf("%d%d%d", &n, &s, &e);

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

        scanf("%d", &x[i]);

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

        scanf("%d", &a[i]);

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

        scanf("%d", &b[i]);

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

        scanf("%d", &c[i]);

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

        scanf("%d", &d[i]);

    valid[][] = ;

    int delta = ;

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

    {

        if(i == min(s, e))

            delta = s < e ?  : -;

        else if(i == max(s, e))

            delta = ;

        if(i != s && i != e)

            for(int j = ; j <= i && j <= n - i; ++j)

            {

                if(j && valid[i - ][j - ])

                    update(f[i][j], f[i - ][j - ] + b[i] + d[i] - x[i] * , valid[i][j]);

                if((j || i == n) && valid[i - ][j + ])

                    update(f[i][j], f[i - ][j + ] + a[i] + c[i] + x[i] * , valid[i][j]);

                if(j && valid[i - ][j])

                {

                    if(j >  || !delta)

                        update(f[i][j], f[i - ][j] + min(a[i] + d[i], b[i] + c[i]), valid[i][j]);

                    else if(delta == )

                        update(f[i][j], f[i - ][j] + a[i] + d[i], valid[i][j]);

                    else

                        update(f[i][j], f[i - ][j] + b[i] + c[i], valid[i][j]);

                }

            }

        else if(i == s)

            for(int j = ; j <= i && j <= n - i; ++j)

            {

                if(s < e && j && valid[i - ][j - ])

                    update(f[i][j], f[i - ][j - ] + d[i] - x[i], valid[i][j]);

                if(s < e && j && valid[i - ][j])

                    update(f[i][j], f[i - ][j] + c[i] + x[i], valid[i][j]);

                if(s > e && (j || i == n) && valid[i - ][j + ])

                    update(f[i][j], f[i - ][j + ] + c[i] + x[i], valid[i][j]);

                if(s > e && j && valid[i - ][j])

                    update(f[i][j], f[i - ][j] + d[i] - x[i], valid[i][j]);

            }

        else

            for(int j = ; j <= i && j <= n - i; ++j)

            {

                if(s < e && (j || i == n) && valid[i - ][j + ])

                    update(f[i][j], f[i - ][j + ] + a[i] + x[i], valid[i][j]);

                if(s < e && j && valid[i - ][j])

                    update(f[i][j], f[i - ][j] + b[i] - x[i], valid[i][j]);

                if(s > e && j && valid[i - ][j - ])

                    update(f[i][j], f[i - ][j - ] + b[i] - x[i], valid[i][j]);

                if(s > e && j && valid[i - ][j])

                    update(f[i][j], f[i - ][j] + a[i] + x[i], valid[i][j]);

            }

    }

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

    return ;

}

巴特西

codeforces 704B - Ant Man [想法题]

最新文章

热门文章