Gym - 101147H H. Commandos —

题目链接：http://codeforces.com/gym/101147/problem/H

题解：

单纯的三维DP。可用递推或记忆化搜索实现。

学习：开始时用记忆化搜索写，dp[]初始化为0，结果一直走不出循环。后来发现：即使被搜过的位置，其值也可以是0，当再一次访问这个位置时，由于其值为0，就误以为这个位置没有搜过，于是再搜一遍。所以就不能用0来判断是否被搜索过。以后记忆化搜索就用-1来初始化dp[]吧，当然最稳的做法就是加个vis[]数组，看情况而定。

递推：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <sstream>

#include <algorithm>

using namespace std;

#define pb push_back

#define mp make_pair

#define ms(a, b)  memset((a), (b), sizeof(a))

//#define LOCAL

#define eps 0.0000001

typedef long long LL;

const int inf = 0x3f3f3f3f;

const int maxn = 200000+10;

const int mod = 1000000007;

int dp[15][15][15];

int a[15][15][15];

void  slove()

{

    int N;

    int f,x,y,h;

    ms(a,0);

    ms(dp,0);

    scanf("%d",&N);

    while(N--)

    {

        scanf("%d%d%d%d",&f,&x,&y,&h);

        a[f][x][y] = h;

    }

    for(int k = 1; k<=10; k++)

    for(int i = 10; i>0; i--)

    for(int j = 10; j>0; j--)

    {

        dp[k][i][j] = a[k][i][j] + max( max(dp[k][i][j+1], dp[k][i+1][j]), dp[k-1][i][j] );

    }

    printf("%d\n",dp[10][1][1]);

}

int main()

{

    #ifdef LOCAL

        freopen("commandos.in", "r", stdin);

//      freopen("output.txt", "w", stdout);

    #endif // LOCAL

    int T;

    scanf("%d", &T);

    while(T--){

        slove();

    }

    return 0;

}

递归（记忆化搜索）;

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <sstream>

#include <algorithm>

using namespace std;

#define pb push_back

#define mp make_pair

#define ms(a, b)  memset((a), (b), sizeof(a))

//#define LOCAL

#define eps 0.0000001

typedef long long LL;

const int inf = 0x3f3f3f3f;

const int maxn = 200000+10;

const int mod = 1000000007;

int dp[15][15][15];

int a[15][15][15];

int dfs(int k, int x, int y)

{

    if(k<1 || x>10 || y>10)

        return 0;

    if(dp[k][x][y]!=-1)// 初始化为-1

        return dp[k][x][y];

    dp[k][x][y] = a[k][x][y] + max( dfs(k-1,x,y), max( dfs(k,x+1,y) ,dfs(k,x,y+1) ) );

    return dp[k][x][y];

}

void  slove()

{

    int N;

    int f,x,y,h;

    ms(a,0);

    ms(dp,-1);

    scanf("%d",&N);

    while(N--)

    {

        scanf("%d%d%d%d",&f,&x,&y,&h);

        a[f][x][y] = h;

    }

    cout<<dfs(10,1,1)<<endl;

}

int main()

{

     #ifdef LOCAL

        freopen("commandos.in", "r", stdin);

//      freopen("output.txt", "w", stdout);

    #endif // LOCAL

    int T;

    scanf("%d", &T);

    while(T--){

        slove();

    }

    return 0;

}

巴特西

Gym - 101147H H. Commandos —— DP

最新文章

热门文章