D - Free Candies UVA

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1059

题目大意：有四堆糖果，称矩阵排列，一共有n行，只能在每一堆的最上方取糖果，病放入篮子中，如果篮子中有相同的颜色的糖果则可以抵消，篮子中最多能盛放5个糖果，当篮子中的

糖果数量达到5个时，游戏结束。问最多能获得多少个糖果。

解法：由于每次都只能从每一堆的最上方取糖果，所以先开一个一维数组用来记录每一堆取到了第几行，再开一个bool数组，用来判断该颜色的糖果有没有出现过。再开一个四维的数组用来记录该状态的最大能取回多少糖果。

#include<iostream>

#include<cstring>

using namespace std;

int n;

int arr[][];

bool pre[];

int dp[][][][];

int toal[];

int dfs(int x){

    if(dp[toal[]][toal[]][toal[]][toal[]]!=-){

        return dp[toal[]][toal[]][toal[]][toal[]];

    }

    if(x==) return ;

    int ans=;

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

        if(toal[i]==n+) continue ;

        int color=arr[toal[i]][i];

        if(pre[color]){

            pre[color]=;

            toal[i]++;

            ans=max(ans,dfs(x-)+);//加一

            toal[i]--;//回溯

            pre[color]=;//回溯

        }

        else {

            pre[color]=;

            toal[i]++;

            ans=max(ans,dfs(x+));//如果没有相同颜色的糖果，则不用加1

            toal[i]--;

            pre[color]=;

        }

    }

//    cout<<ans<<endl;

    return dp[toal[]][toal[]][toal[]][toal[]]=ans;

}

int main(){

    cin>>n;

    for(int i = ;i<=n;i++)

        for(int j=;j<=;j++){

            cin>>arr[i][j];

        }

    memset(dp,-,sizeof(dp));

    memset(pre,,sizeof(pre));

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

        toal[i]=;

    }

    cout<<dfs()<<endl;

    return ;

}

总结：再写dfs的时候，如果定义为int类型，一定要先清楚，，返回值的意义。

巴特西

D - Free Candies UVA - 10118

最新文章

热门文章