题目描述

blablabla

样例

blablabla

算法1

不难看出是一个简单的dp，但有一个坑，因为C_i可能为0，所以a[i][j]++，否则边界不好处理。

blablabla

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int Mod=1000000007;
const int N=55;
ll n,m,t,a[N][N];
ll dp[N][N][N][N];
int main()
{
    freopen("lx.in","r",stdin);
    cin>>n>>m>>t;
    int maxn=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)  cin>>a[i][j],a[i][j]++;  

    memset(dp,0,sizeof(dp));
    dp[1][1][0][0]=1;
    dp[1][1][1][a[1][1]]=1; 

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            if(i==1&&j==1) continue;
            for(int k=0;k<=t;++k){
                int res=0;
                for(int l=0;l<=13;++l)
                {
                    if(i>1) dp[i][j][k][l]+=dp[i-1][j][k][l]%Mod;
                    if(j>1) dp[i][j][k][l]+=dp[i][j-1][k][l]%Mod;
                    if(a[i][j]>l) res+=dp[i-1][j][k-1][l]+dp[i][j-1][k-1][l]%Mod;
                }
                dp[i][j][k][a[i][j]]+=res%Mod;
            }
        }
    ll ans=0;
    for(int i=0;i<=13;++i)
        ans+=dp[n][m][t][i]%Mod;
    cout<<ans<<endl;
    /*
    dp[i][j][k][l]=dp[i-1][j][k][l]+dp[i][j-1][k][l];       //dp[i][j][k] 表示i,j位置为终点时取k个宝藏 的方案数 
    if(a[i][j]>l) dp[i][j][k][a[i][j]]=dp[i-1][j][k-1][l]+dp[i][j-1][k-1][l];
    */

    return 0;
}