Dynamic programming solution of 2014 Blue Bridge Cup

2021-03-02 21:48:28

Blue Bridge Cup 2014 The real topic of the year Palace of the Earth takes treasure Dynamic programming solution

Title Description

X The king has a treasure house . yes n x m Matrix of lattice . One treasure per cell . Every baby has a value tag .

The entrance to the underground palace is in the upper left corner , The exit is in the lower right corner .

Xiaoming is taken to the entrance of the underground palace , The king asked him to walk only to the right or down .

When walking through a grid , If the treasure in that lattice is worth more than any treasure in Xiaoming's hand , Xiaoming can pick it up （ Of course , Or not ）.

When Xiaoming comes to the exit , If the baby in his hand happens to be k Pieces of , Then these babies can be given to Xiao Ming .

Please help Xiao Ming figure it out , In a given situation , How many different action plans does he have k Baby .

Input

The input line 3 It's an integer , Separate with spaces ：n m k (1< =n,m< =50, 1< =k< =12)

Next there is n Row data , Each row has m It's an integer Ci (0< =Ci< =12) Represents the value of the treasure on this grid

If you use it directly dfs Violent search , Will not pass the test , But the introduction of mnemonics will be able to prune and avoid a lot of repeated calculations . We know that if a problem can be decomposed into many small problems , And the small problems are independent of each other , So we can use dynamic programming to deal with .

1. First Definition dp Array

dp[i][j][k][c]: From $$(1, 1)$$ Go to the $$(i,j)$$ when , I have $$k$$ Baby , And the maximum value of the baby is $$c$$ The number of action plans at the time .

2. find State transition equation

According to the title , Xiao Ming can only walk down or right , be $$(i,j)$$ The state should be $$(i-1,j)$$ and $$(i,j-1)$$ The state of the world has changed , Yes $$dp[i][j]=dp[i-1][j]\quad OP \quad dp[i][j-1]$$,（OP Represents an operation ）.

I know when I walk through a grid , If the treasure in that lattice is worth more than any treasure in Xiaoming's hand , Xiaoming can pick it up （ Of course , Or not ）, hypothesis The value of the treasure in the current grid is cur be ：

If you take the baby at this time ：$$dp[i][j][k][cur]+=dp[i-1][j][k-1][0...cur-1]+dp[i][j-1][k-1][0...cur-1]$$

//  Take the baby
for (int c = 0; c < cur; c++) {
dp[i][j][k][cur] += dp[i - 1][j][k - 1][c] + dp[i][j - 1][k - 1][c];
}


If you don't take the baby ：$$dp[i][j][k][c]+=dp[i-1][j][k][c]+dp[i][j-1][k][c]$$,(c = 0, 1, 2 ... 12)

//  Don't take the baby
for (int c = 0; c <= 12; c++) {
dp[i][j][k][c] += dp[i - 1][j][k][c] + dp[i][j - 1][k][c];
}


3.base case

set up $$(i,j)$$ The value of being a baby $$a[i][j]$$ Serve as k = 1 when ,$$dp[i][j][1][a[i][j]]$$ Only the current baby is selected , It is known that the number of schemes is from $$(1, 1)$$ Go to the $$(i,j)$$ Number of alternatives .

Definition $$DP[i][j]$$ From $$(1, 1)$$ Go to the $$(i,j)$$ Number of alternatives , Easy to know $$DP[i][j] = DP[i - 1][j] + DP[i][j-1]$$,

Then there are $$dp[i][j][1][a[i][j]]+=dp[i-1][j][1][a[i-1][j]]+dp[i][j-1][1][a[i][j-1]]$$

// base case
dp[1][1][1][a[1][1]] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j][1][a[i][j]] += dp[i-1][j][1][a[i-1][j]] + dp[i][j-1][1][a[i][j-1]];
}
}


Code ：

import java.util.Scanner;

public class Main {
static int MAXN = 50, MAXM = 50;
static int MAXK = 12, MAXC = 12;
static long[][][][] dp = new long[MAXN + 1][MAXM + 1][MAXK + 1][MAXC + 1];
static int[][] a = new int[MAXN + 1][MAXM + 1];
static int n, m, k, ans = 0, mod = 1000000007;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = sc.nextInt();

// base case
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)) {
dp[i][j][1][a[i][j]] += dp[i-1][j][1][a[i-1][j]] + dp[i][j-1][1][a[i][j-1]];
dp[i][j][1][a[i][j]] %= mod;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int l = 1; l <= k; l++) {
int cur = a[i][j];
//  Take the baby
for (int c = 0; c < cur; c++) {
dp[i][j][l][cur] += dp[i-1][j][l-1][c] + dp[i][j-1][l-1][c];
dp[i][j][l][cur] %= mod;
}
//  Don't take the baby
for (int c = 0; c <= MAXC; c++) {
dp[i][j][l][c] += dp[i-1][j][l][c] + dp[i][j-1][l][c];
dp[i][j][l][c] %= mod;
}
}

for (int c = 0; c <= MAXC; c++) {
ans += dp[n][m][k][c];
ans %= mod;
}

System.out.println(ans);
}
}


Maximum time complexity $$O(T)=O(i*j*k*c)=O(50*50*12*13)=O(390000)$$

https://chowdera.com/2021/03/20210302214758179S.html