C. Arcade dp二维费用背包 + 滚动数组玄学

http://codeforces.com/gym/101257/problem/C

询问从左上角走到右下角，每次只能向右或者向左，捡起三种物品算作一个logo，求最多能得到多少个logo。

设dp[i][j][k][h]表示走到(i, j)这个格子，然后得到的第一种物品是k，第二种物品是h的时候，能得到的第三个物品的最大值是多少。

-inf表示不存在这个状态，其实第三种物品可以算出来，因为一共的步数就是i + j - 1，所以捡起的物品数量是固定的。

所以直接这样dp下去即可，是一个背包问题。

然后会MLE，所以我把第一维滚动了。（不会把第二维也滚动，一直出不了样例）

有一个小bug就是，每种物品最多都是可以捡200个，n + m - 1个，一定要都枚举是否成立。

一开始我只枚举到67个，因为67 * 3 = 201，logo数目其实最多就是66

但是会wa。还想不到数据

可能dp应该是要遍历所有可能的结果，只不过是选最优，有一些部分被抛弃了而已。

所以枚举到200吧，毕竟它最多能捡起200个。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e2 + ;

char str[maxn][maxn];

int n, m;

int dp[][maxn][ + ][ + ];

int pre(int id) {

    if (id == ) return ;

    else return id - ;

}

void work() {

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

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

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

    }

    memset(dp, -0x3f, sizeof dp);

    dp[][][][] = ;

    dp[][][][] = ;

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

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

            int en = i + j - ;

            for (int k = en; k >= ; --k) {

                for (int h = en; h >= ; --h) {

                    dp[i % ][j][k][h] = -inf;

                    if (str[i][j] == '>') {

                        if (k < ) {

                            dp[i % ][j][k][h] = -inf;

                            continue;

                        }

                        dp[i % ][j][k][h] = dp[pre(i % )][j][k - ][h];

                        dp[i % ][j][k][h] = max(dp[i % ][j][k][h], dp[i % ][j - ][k - ][h]);

                    } else if (str[i][j] == '|') {

                        if (h < ) {

                            dp[i % ][j][k][h] = -inf;

                            continue;

                        }

                        dp[i % ][j][k][h] = dp[pre(i % )][j][k][h - ];

                        dp[i % ][j][k][h] = max(dp[i % ][j][k][h], dp[i % ][j - ][k][h - ]);

                    } else {

                        dp[i % ][j][k][h] = dp[pre(i % )][j][k][h] + ;

                        dp[i % ][j][k][h] = max(dp[i % ][j][k][h], dp[i % ][j - ][k][h] + );

                    }

                }

            }

        }

    }

    int ans = ;

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

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

            ans = max(ans, min(i, min(j, dp[n % ][m][i][j])));

//            if (dp[n % 3][m][i][j] >= 0) {

//                cout << i << " " << j << " " << dp[n % 3][m][i][j] << endl;

//            }

        }

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

C. Arcade dp二维费用背包 + 滚动数组玄学

最新文章

热门文章

巴特西

C. Arcade dp二维费用背包 + 滚动数组 玄学

最新文章

热门文章

C. Arcade dp二维费用背包 + 滚动数组玄学