경동 필기시험 문제-보물찾기 dp해석

화전북풍천진대학 인지계산 및 응용중점실험실일자: 2015/9/24
경동 필기시험 문제는 블루 브리지 컵의 원제라고 한다.동적 기획으로 해답을 구하는 문제를 생각하기 쉽다.행렬 보물찾기는 가치가 점차적으로 증가하는 것만 선택할 수 있고 k개를 선택할 수 있는 방안이 몇 가지가 있습니까?DP 구해, 맨 위에서 아래로 dp 해법 상태 정의 dp[i] [j] [value] [num]: 맨 위에서 아래로 행렬 i, j 요소를 구할 때 최대 가치는value, 선택한 개수는num의 방안 수입니다.상태 이동: 두 단계로 나뉜다(두 가지 상황이 아니라는 것을 주의한다): 1. i에서 j개의 칸을 선택하지 않을 때 이 상태로 옮길 수 있는 방안의 수를 더하면 된다.2. 제i를 선택하고 j개의 네모난 보물을 선택하면 현재 상태 안에 있는value<보물 가치의 상태를 갱신한다(현재 보물을 선택하면 이 상태로 옮길 수 있는 종류수를 선택한다) 여기서 초기 문제를 풀 수 있다. 필기시험에서 제i, j개의 네모난 보물을 선택할 때 dp[i][j][temp][1]이 얼마나 증가했는지 이해하지 못했다.실제로 여기에 증가한 수는 (1,1)에서 (i,j)까지의 격자 경로수이다.위의 이 상태가 처음 풀리는 것을 알아차리기만 하면 이 문제는 매우 간단하다.

#include <iostream>
#include <fstream>
using namespace std;

#define maxRow 15
#define maxCol 15
#define maxVal 15
#define maxNum 15

int value[maxRow][maxCol];
int dp[maxRow][maxCol][maxVal][maxNum];
int routeCount[maxRow][maxCol];

int RouteCountFunction(int m, int n)
{
    if (routeCount[m][n] > 0)
        return routeCount[m][n];
    if ((m == 1) || (n == 1))
    {
        routeCount[1][1] = 1;
        routeCount[m][n] = 1;
        return 1;
    }
    routeCount[m][n] = RouteCountFunction(m - 1,n) + RouteCountFunction(m,n - 1);
    return routeCount[m][n];
}

void DPfunc(int m, int n,int total)
{
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int val = 0; val < maxVal; val++)
                for (int count = 0; count < maxNum; count++)
                    dp[i][j][val][count] = dp[i - 1][j][val][count] + dp[i][j - 1][val][count];
            int temp = value[i][j];
            dp[i][j][temp][1] += routeCount[i][j];
            for (int q = 2; q <= total; q++)
                for (int k = 0; k < temp; k++)
                    dp[i][j][temp][q] += dp[i - 1][j][k][q - 1] + dp[i][j - 1][k][q - 1];
        }
}
int main()
{
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
    int m, n, k;
    cin >> m >> n >> k;
    memset(dp, 0, sizeof(dp));
    memset(routeCount, 0, sizeof(routeCount));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> value[i][j];
    RouteCountFunction(m, n);
    DPfunc(m, n, k);
    int result = 0;
    for (int i = 0; i<12; i++)
        result += dp[m][n][i][k];
    cout << result << endl;

    system("pause");
    return 0;
}