P1043 【数字游戏】

DinnerHunt · 2018-01-06 17:51:22 · 题解

- 搜索

翻了下题解发现全是用DP做的，这里我发一份DFS的题解吧

• 大致思路就是从N个节点，依次进行依次DFS搜索操作，然后进行剪枝

• 搜索部分

• • 首先我们选取任意一个点，将圆拆称链，因为是区域划分，所以必须是连续的一段，所以，下一部分的起点一定是这部分的终点加一，而又因为每个区域最好包含一个点，所以当前区域可选最大节点数量为 N-M+D(N为节点数，M为区域数，D为当前深度)

• 剪枝部分

• • 这里进行一点小的可行性剪枝，如果当前的值最大无法超过最大值，最小无法小于最小值，则剪枝。因为每个部分的值都为1-9，所以我们可以求出当前值所能构成的最大最小值

• 最后部分

• • 遍历每个点的开始的链，然后在DFS中记得调整

    //P1043 数字游戏
    //DinnerHunt
    #include <cstdio>
    using namespace std;
    const int maxn = 100000;
    inline int min(int x,int y){
        return x<y?x:y;
    }
    inline int max(int x,int y){
        return x>y?x:y;
    }
    inline int mod(int x){
        if(x<0) x+=maxn;
        return x%10;
    }
    inline int pow(int x){
        int k=1;
        for(int i=0;i<=x;i++)
            k*=9;
        return k;
    }
    int n,m,arr[55],mx=0,mi = maxn;
    void dfs(int d,int s,int sound,int x){  //当前深度,当前点的位置，环的第几部分，当前的值
        int a = 0;
        if(x*pow(m-d)<=mx&&x>=mi) return;
        if(d==m){
            for(int i=s;i-sound<=n;i++){
                a+=arr[(i-1)%n+1];
            }
            x*= mod(a);
            mi = min(mi,x);
            mx = max(mx,x);
            return;
        }
        for(int i=s;i-sound<=n-d;i++){
            a+=arr[(i-1)%n+1];
            dfs(d+1,i+1,sound,x*mod(a));
        }
        return;
    }
    int main(){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&arr[i]);
        }
    }
        for(int i=0;i<n;i++)
            dfs(1,i+1,i,1);
        printf("%d\n%d",mi,mx);
return 0;