当前位置:网站首页>Dynamic programming solution of 2014 Blue Bridge Cup

Dynamic programming solution of 2014 Blue Bridge Cup

2021-03-02 21:48:28 Code-CHAN

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

Answer key

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)\)

版权声明
本文为[Code-CHAN]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/03/20210302214758179S.html