(动态规划)

$f[x][y][i][j]$ 表示在(x,y)时获得i件宝物中最大价值的是y的走法。

C++ 代码

#include <iostream>

using namespace std;

const int N=60,M=15,mod=1000000007;
typedef long long LL;

int n,m,k;
int a[N][N];
LL f[N][N][M][M];

int main(){
    cin>>n>>m>>k;

    for(int x=1;x<=n;++x){
        for(int y=1;y<=m;++y){
            int w;
            cin>>w;
            w++;
            if(x==1&&y==1) {
                f[1][1][1][w]=1;
                f[1][1][0][0]=1;
                continue;
            }
            // 拿
            for(int i=0;i<k;++i){
                for(int j=0;j<w;++j){
                    f[x][y][i+1][w]+=f[x-1][y][i][j]+f[x][y-1][i][j];
                    f[x][y][i+1][w]%=mod;
                }
            }
            // 不拿
            for(int i=0;i<=k;++i){
                for(int j=0;j<=13;++j){
                    f[x][y][i][j]+=f[x-1][y][i][j]+f[x][y-1][i][j];
                    f[x][y][i][j]%=mod;
                }
            }
        }
    }
    LL ans=0;
    for(int i=0;i<=13;++i) (ans+=f[n][m][k][i])%=mod;
    cout<<ans<<endl;

    return 0;
}