(dp)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,m,c,cnt;
const int N=55,mod=1000000007;
int a[N][N];
int f[N][N][N][16];//在(i, j)这个点，拿了cnt个物品，这些物品中价值最大的是k
int main()
{
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>a[i][j];a[i][j]++;//价值可能为0 避免边界问题  每个价值都加一
    }
     //边界处理   结果求的是方案数 则f[1][1][0][0]=1;
     f[1][1][1][a[1][1]]=1;f[1][1][0][0]=1;
     for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     for(int cnt=0;cnt<=c;cnt++)
     for(int k=0;k<14;k++)
     {
         //不选ij
         f[i][j][cnt][k]=(f[i][j][cnt][k]+f[i-1][j][cnt][k])%mod;
         f[i][j][cnt][k]=(f[i][j][cnt][k]+f[i][j-1][cnt][k])%mod;
         //选ij
         if(k==a[i][j])
         {
             for(int s=0;s<a[i][j];s++)
             {
                 f[i][j][cnt][k]=(f[i][j][cnt][k]+f[i-1][j][cnt-1][s])%mod;
                 f[i][j][cnt][k]=(f[i][j][cnt][k]+f[i][j-1][cnt-1][s])%mod;
             }
         }
     }
     int res=0;
     for(int i=1;i<=14;i++)
     {
         res=(res+f[n][m][c][i])%mod;
     }
     cout<<res<<endl;
     return 0;
}