最长上升子序列+数字三角形

$ 时间复杂度O(NMKCC),空间复杂度O(NMKC) $

参考文献

蓝桥杯辅导课

AC代码

#include <iostream>
using namespace std;

const int N = 55, K = 15, C = 15, P = 1000000007;

int n, m , k;
int w[N][N], f[N][N][K][C];


int main(){
    //读入
    cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++){
            cin >> w[i][j];
            w[i][j] ++;
        }


    //初始状态
    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1;

    //DP
    for (int i = 1 ; i <= n ; i ++){
        for (int j = 1 ; j <= m ; j ++){
            if (i == 1 && j == 1) continue;
            for (int u = 0 ; u <= k ; u ++){
                for (int c = 0 ; c <= 13 ; c ++){
                    int &t = f[i][j][u][c];
                    //不取
                    t = (t + f[i - 1][j][u][c]) % P;
                    t = (t + f[i][j - 1][u][c]) % P;
                    if (u > 0 && c == w[i][j]){
                        //取,枚举接到比自己小的后面
                        for (int v = 0 ; v < c ; v ++){
                            t = (t + f[i - 1][j][u - 1][v]) % P;
                            t = (t + f[i][j - 1][u - 1][v]) % P;
                        }

                    }
                }
            }
        }
    }

    //输出答案
    int res = 0;
    for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % P;

    cout << res;

    return 0;

}