题解 P1043 【数字游戏】

· · 题解

普及组第二题竟然是绿题，蒟蒻的我瑟瑟发抖

思路

该死的DP太难打了，于是我选择直接暴力枚举DFS。

主函数

首先，为了枚举环的起点，需要破环为链，开一个2倍空间的数组记录。

枚举起点时，先dfs，再把整个数组往前挪一位，这样就不用管开始位置的问题了。

最后输出答案。

求模10的余数

这个函数有一个细节：如果原数为负数，则%10之后还是负数。（如(-11)%10=-1）

解决方法：先%10（保证不会小于-10），再+10（变成正数），最后%10（正数+10>10）。

DFS

1.参数：depth深度；now当前位置；value当前的积

2.结束条件：depth==m

3.满足结束条件时：{

1)算出剩余数的和，并与value相乘

2)与两个答案作比较

}

4.下一步深搜：{

1)从now遍历到n-m+depth（再往后就取不到了）

2)用变量sum记录a数组从now开始的前缀和（就是从a[now]一直加到a[i]的和）

3)进行下一步深搜，注意now是i+1

}

5.（最重要的）剪枝：当value>=最小答案且value*9^{m-depth+1}<=最大答案时，就可以剪枝。如果不剪枝，第4个测试点就需要约1000秒的时间（本人亲身经历）

代码

我相信没几个人会喜欢上面的一通分析的吧，那么，你们喜欢的代码来了——

#include<cstdio>
#include<algorithm>//算法库，有max和min
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;//定义成2e9或2147483647也行
const int n9[9]={9,81,729,6561,59409,531441,4782969,43046721,387420489};//m<=9，打个表就好了
int n,m;
int a[MAXN];
int ansmin=INF,ansmax=0;//最小和最大，都要初始化
int mod10(int x){//计算模10的函数
    return (x%10+10)%10;
}
void dfs(int depth,int now,int value){//重磅dfs
    if(value>=ansmin&&value*n9[m-depth]<=ansmax) return;//剪枝
    int sum=0;
    if(depth==m){
        for(int i=now;i<=n;i++) sum+=a[i];//计算和
        ansmin=min(ansmin,value*mod10(sum));//比较
        ansmax=max(ansmax,value*mod10(sum));
        return;
    }
    for(int i=now;i<=(n-m+depth);i++){//遍历下一个点
        sum+=a[i];//前缀和
        dfs(depth+1,i+1,value*mod10(sum));//下一步计算
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i+n]=a[i];//破环成链
    }
    for(int i=1;i<=n;i++){//枚举初始点
        dfs(1,1,1);//都是1，只是巧合
        for(int j=1;j<=2*n;j++) a[j]=a[j+1];//往前挪
    }
    printf("%d\n%d\n",ansmin,ansmax);//输出
    return 0;//华丽结束
}

不要复制完代码就走了啊，这样是不道德的，思路也是要看的，对了，别忘了要点个赞！