题目描述
blablabla
样例
# include<iostream>
# include<algorithm>
using namespace std;
int dp[55][55][15][15] = {0};
int map[55][55];
int mod = 1000000007;
int main() {
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> map[i][j];
map[i][j] ++;
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m ; j++) {
if(i == 1 && j == 1) {
dp[1][1][1][map[1][1]] = 1; // 取初始点的物品
dp[1][1][0][0] = 1; // 不取初始点的物品
continue;
}
for(int curK = 0; curK <= k; curK ++) {
for(int maxPrice = 0; maxPrice <= 13; maxPrice ++) {
// 不拿物品
dp[i][j][curK][maxPrice] = (dp[i][j][curK][maxPrice] + dp[i - 1][j][curK][maxPrice]) % mod;
dp[i][j][curK][maxPrice] = (dp[i][j][curK][maxPrice] + dp[i][ j - 1 ][curK][maxPrice]) % mod;
// 拿物品
if (curK > 0 && maxPrice == map[i][j]) {
for (int tmp = 0; tmp < map[i][j]; tmp++ ) {
dp[i][j][curK][maxPrice] = (dp[i][j][curK][maxPrice] + dp[i - 1][j][curK - 1][tmp])%mod;
dp[i][j][curK][maxPrice] = (dp[i][j][curK][maxPrice] + dp[i][j - 1][curK - 1][tmp])%mod;
}
}
}
}
}
}
// for(int i = 1; i <= n; i ++) {
// for(int j = 1; j <= m ; j++) {
// for(int curK = 0; curK <= k; curK ++) {
// for(int maxPrice = 0; maxPrice <= 2; maxPrice ++) {
// cout << "debug: ( " << i << " , " << j << " ) curK: " << curK << " maxPrice: " << maxPrice << " dp: " << dp[i][j][curK][maxPrice] << endl;
// }
// }
// }
// }
int res = 0;
for(int maxPrice = 0; maxPrice <= 13; maxPrice ++) {
res = (res + dp[n][m][k][maxPrice])%mod;
}
cout << res << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla