AtCoder - agc043_a 和 POJ

题意：

给你一个n行m列由'#'和'.'构成的矩阵，你需要从(1,1)点走到(n,m)点，你每次只能向右或者向下走，且只能走'.'的位置。

你可以执行操作改变矩阵：

你可以选取两个点，r0,c0;r1,c1。以(r0,c0)为小矩阵左上角坐标，以(r1,c1)为小矩阵右下角坐标。你要把这个小矩阵中的所有字符反转（也就是原来是'#'的，要变成'.'，原来是'.'的，要变成'#'）

题解：

对于样例

3 3

.##

.#.

##.

我们可以看成反转之后的矩阵最终从(1,1)走到(n,m)的只有一条路径，不管其他点(如下，*号就是我们最终选择的路径)

3 3

.*#

.*.

#*.

那么我们就可以反转(1,1)和(2,3)这个小矩阵,或者(2,1)，(2,3)这个小矩阵。(1,1)和(2,3)这个小矩阵反转的时候虽然涉及到了一些其他点（第一列所有点），但是我们最终要走的路径没有用到它，所以不用管它。

代码：

#include <bits/stdc++.h>

typedef long long ll;

const int maxn = 1e2 + 10;

const int INF = 0x3f3f3f3f;

char s[maxn][maxn];

int dp[maxn][maxn];

int min(int a, int b)

{

    if (a < b)

        return a;

    else

        return b;

}

int max(int a, int b)

{

    if (a > b)

        return a;

    else

        return b;

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

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

    {

        scanf("%s", s[i] + 1);

    }

    dp[1][1] = (s[1][1] == '#');

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

    {

        for (int j = 1; j <= m; ++j)

        {

            if (i == 1 && j == 1)

                continue;

            char ch = s[i][j];

            dp[i][j] = INF;

            if (i > 1)

            {

                if (s[i - 1][j] == ch)

                    dp[i][j] = min(dp[i][j], dp[i - 1][j]);

                else

                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + (ch == '#'));

            }

            if (j > 1)

            {

                if (s[i][j - 1] == ch)

                    dp[i][j] = min(dp[i][j], dp[i][j - 1]);

                else

                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + (ch == '#'));

            }

        }

    }

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

    return 0;

}

POJ - 2336 题意：

现在有m辆车在左岸，你需要用一艘船把所有车运送到右岸，每次船只能运送n辆车。船过河的时间为t（也就是一来一回所需时间2*t）。

问你把所有车运送到右岸最少是什么时候，在这个基础上给出最少运送次数（运送次数不算船从右岸返回到左岸）

题目给你m辆车到达左岸的时间点vi。

题解：

暴力转移dp，dp[i]表示把前i辆车运送到右岸之后船又回到左岸的最小时间点

dp[i]=max(dp[j],v[i]); (1<=j<=i<=n)

dp[i]+=2*t;

cnt[i]=cnt[j]+1;

代码：

#include <stdio.h>

#include <algorithm>

#include <iostream>

using namespace std;

const int maxn = 2e3 + 10;

const int INF=0x3f3f3f3f;

int max(int a,int b)

{

    if(a>b) return a;

    else return b;

}

int v[maxn],cnt[maxn],dp[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,t,m;

        scanf("%d%d%d",&n,&t,&m);

        for(int i=1;i<=m;++i)

        {

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

        }

        for(int i=1;i<=m;++i)

        {

            dp[i]=INF;

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

            {

                if(dp[i]>max(dp[j],v[i]))

                {

                    dp[i]=max(dp[j],v[i]);

                    cnt[i]=cnt[j]+1;

                }

            }

            dp[i]+=2*t;

        }

        printf("%d %d\n",dp[m]-t,cnt[m]);

    }

    return 0;

}

巴特西

AtCoder - agc043_a 和 POJ - 2336 dp

最新文章

热门文章