[蓝桥杯]地宫取宝

一道值得思考的动规题,有很多细节都需要注意。

#include <bits/stdc++.h>
#define ll long long
#define MAXN 51
#define MAXK 13
#define MOD 1000000007
#define f(a,b,c) for(int a=b;a<=c;++a)
using namespace std;

int n,m,k;
int G[MAXN][MAXN];

/*
骗分暴力

int ans;


void dfs(int x,int y,int num,int max) {
    if(num > k || x > n || y > m)
        return;

    if(x == n && y == m) {
        if(num == k)
            ans = (ans + 1) % MOD;

        if(num == k - 1 && G[x][y] > max)
            ans = (ans + 1) % MOD;
    }

    if(G[x][y] > max) {
        dfs(x+1,y,num+1,G[x][y]);
        dfs(x,y+1,num+1,G[x][y]);
    }

    dfs(x+1,y,num,max);
    dfs(x,y+1,num,max);
}

int main() {
    ios::sync_with_stdio(false);

    cin>>n>>m>>k;

    f(i,1,n)
        f(j,1,m)
            cin>>G[i][j];

    dfs(1,1,1,G[1][1]);

    cout<<ans;

    return 0;
}

*/

int maxv;
ll ans;
int dp[MAXN][MAXN][MAXK][MAXK];
// i行j列取c个宝物最大价值为v

int main() {
    ios::sync_with_stdio(false);

    cin>>n>>m>>k;

    f(i,1,n)
        f(j,1,m) {
            cin>>G[i][j];
            ++G[i][j];
            //处理价值为0的宝物
            maxv = max(maxv,G[i][j]);
            //记录最大价值
        }

    dp[1][1][0][0] =  dp[1][1][1][G[1][1]] = 1;
    //初始化,第一件物品拿与不拿

    f(i,1,n)
        f(j,1,m)
            f(c,0,k)
                f(v,0,maxv) {
                    if(i <= n - 1) {
                        if(G[i+1][j] > v)
                            dp[i+1][j][c+1][G[i+1][j]] = (dp[i+1][j][c+1][G[i+1][j]] + dp[i][j][c][v]) % MOD;
                        //拿
                        dp[i+1][j][c][v] = (dp[i+1][j][c][v] + dp[i][j][c][v]) % MOD;
                        //不拿
                    }

                    if(j <= m - 1) {
                        if(G[i][j+1] > v)
                            dp[i][j+1][c+1][G[i][j+1]] = (dp[i][j+1][c+1][G[i][j+1]] + dp[i][j][c][v]) % MOD;
                        dp[i][j+1][c][v] = (dp[i][j+1][c][v] + dp[i][j][c][v]) % MOD;
                    }
                }

    f(i,0,maxv) 
        ans = (ans + dp[n][m][k][i]) % MOD;
    //把每种最高价值相加

    cout<<ans;

    return 0;
}
Last modification:July 30th, 2019 at 09:41 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment