HDU- 탈옥 DP Or 메모리 검색

4719 단어 HDU
이 문제에서 주의해야 할 것은 두 개의 단점을 구성한 다음에 직접 상태를 개척하는 것이다. dp[i][j]는 i, j 사이의 죄수들이 모두 구해낸 가장 적은 금화수를 나타낸다. 이때의 경계를 주의하면 i, j는 찾지 않는다.초기 조건은 dp[i][i+1] = 0.
코드는 다음과 같습니다.
#include <cstring>

#include <cstdlib>

#include <cstdio>

#include<iostream>

using namespace std;



const int inf = 0x3fffffff;

int N, P, loc[105], dp[105][105];



int dfs(int a, int b)

{

     if(b - a == 1) return 0;

    if (dp[a][b] ) return dp[a][b];

    int ret = inf;

    for(int c = a+1; c < b; c++){

        ret = min(ret,dfs(a,c)+dfs(c,b)+(loc[b]-loc[a])-2 );    

    }

    dp[a][b] = ret;

    return ret;

}



int main()

{

    int T, ca = 1; 

    for (scanf("%d", &T); ca <= T; ++ca) {

        scanf("%d %d", &N, &P);

        loc[0] = 0;

        loc[P+1] = N+1;

        for (int i = 1; i <= P; ++i) {

            scanf("%d", &loc[i]); //         

        }

        P += 1;

        memset(dp,0,sizeof(dp));

    /*    for(int gap = 2; gap <= P; gap++){

            for(int a = 0; a+gap <= P; a++){

                int b = a+gap;

                int ret = inf;

                for(int c = a+1; c < b; c++){

                    ret = min(ret,dp[a][c]+dp[c][b]+(loc[b]-loc[a]-2));    

                }    

                dp[a][b] = ret;

            }    

        }  */

//        printf("Case #%d: %d
", ca, dp[0][P]);
printf("Case #%d: %d
", ca, dfs(0, P)); } return 0; }

좋은 웹페이지 즐겨찾기