流浪者与宝藏

最优题解

考虑动态规划，用表示所在位置横坐标不超过,纵坐标不超过的情况下用掉把钥匙最多可以获得多少金币。那么这个地方如果使用钥匙，那么最多可以获得 这么多的金币。如果不使用钥匙的最大值就是此处的dp值。两者取其大。
时间复杂度和空间复杂度都是

int dp[505][505][6];
int mp[505][505];
int solve(int n, int k,vector<int> &x, vector<int> &y, vector<int> &a){
    memset(dp, 0, sizeof dp);
    memset(mp, 0, sizeof mp);
    assert(x.size() ==n && y.size() == n);
    for(int i = 0; i < n; ++i) mp[x[i]][y[i]] = max(mp[x[i]][y[i]],a[i]);
    int ans = 0;
    for(int i = 1; i <= 500; ++i){
        for(int j = 1; j <= 500; ++j){
            for(int t = 1; t <= k; ++t){
                dp[i][j][t] = dp[i-1][j-1][t-1]+mp[i][j];
                dp[i][j][t] = max(dp[i][j][t], dp[i-1][j][t]);
                dp[i][j][t] = max(dp[i][j][t], dp[i][j-1][t]);
                ans = max(dp[i][j][t], ans);
            }
        }
    }return ans;
}