Gym – 101147H H. Commandos DAG

H - 记忆里在微甜 DAG

 Source

Gym - 101147H

My Solution

题意：即普通的DAG加了一维。

DAG上的dp

三维的有向无环图上dp，

dp[k][i][j] = max(dp[k][i][j], dp[k][i+1][j] + mp[k][i][j]);

dp[k][i][j] = max(dp[k][i][j], dp[k][i][j+1] + mp[k][i][j]);

dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j] + mp[k][i][j]);

复杂度 O(n^3)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

int dp[12][12][12], mp[12][12][12];

int main()
{
    freopen("commandos.in", "r", stdin);
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    int T, n, f, y, x, i, j, k;
    cin >> T;
    while(T--){
        memset(dp, 0, sizeof dp);
        memset(mp, 0, sizeof mp);
        cin >> n;
        for(i = 1; i <= n; i++){ cin >> f >> y >> x;
            cin >> mp[f][y][x];
        }
        for(k = 1; k <= 10; k++){ for(i = 10; i >= 1; i--){
                for(j = 10; j >= 1; j--){
                    dp[k][i][j] = max(dp[k][i][j], dp[k][i+1][j] + mp[k][i][j]);
                    dp[k][i][j] = max(dp[k][i][j], dp[k][i][j+1] + mp[k][i][j]);
                    dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j] + mp[k][i][j]);
                }
            }

        }
        cout << dp[10][1][1] << "n";

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx