问一下为什么DFS会WA+TLE感觉dfs的深度不深？

liukairui @ 2019-07-12 14:27:53

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;

stack<int>ans;
bool is_z[20050],flag=false;
int zsb[2500],n,cur=0;

void dfs(int now,int rest,int summary){
    if(summary>n)return;
    if(now==cur-1&&(rest!=1||is_z[n-summary]==false))return;
    if(rest==1&&is_z[n-summary]==true){ans.push(n-summary);return;}
    if(rest==1&&is_z[n-summary]==false)return;
    //±ß½ç 
    dfs(now,rest-1,summary+zsb[now]);
    if(flag==true){ans.push(zsb[now]);return;}
    dfs(now+1,rest-1,summary+zsb[now]);
    if(flag==true){ans.push(zsb[now]);return;}
    dfs(now+1,rest,summary);
    if(flag==true){ans.push(zsb[now]);return;}
    return;
}

int main(){
    cin>>n;
    //¹¹ÔìËØÊý±í
    memset(is_z,true,sizeof(is_z));
    for(int i=2;i<=sqrt(n*3);i++){
        if(is_z[i]==false)continue;
        for(int j=2;j*i<=n*3;j++)is_z[i*j]=false;
    }
    for(int i=2;i<=n;i++)if(is_z[i]==true)zsb[cur++]=i;
    //dfs
    for(int i=0;i<cur;i++){
        dfs(0,3,0);  //dfs(now,ÒѾ­Ñ¡Á˼¸¸öÊý,summary)
    }
    for(int i=0;i<3;i++){cout<<ans.top()<<" ";ans.pop();}
    return 0;
}

by Gary818 @ 2019-07-12 14:41:59

@liukairui
UTF—8炸了

by liukairui @ 2019-07-12 14:48:14

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;

stack<int>ans;
bool is_z[20050],flag=false;
int zsb[2500],n,cur=0;

void dfs(int now,int rest,int summary){
    if(summary>n)return;
    if(now==cur-1&&(rest!=1||is_z[n-summary]==false))return;
    if(rest==1&&is_z[n-summary]==true){ans.push(n-summary);return;}
    if(rest==1&&is_z[n-summary]==false)return;
    //边界 
    dfs(now,rest-1,summary+zsb[now]);
    if(flag==true){ans.push(zsb[now]);return;}
    dfs(now+1,rest-1,summary+zsb[now]);
    if(flag==true){ans.push(zsb[now]);return;}
    dfs(now+1,rest,summary);
    if(flag==true){ans.push(zsb[now]);return;}
    return;
}

int main(){
    cin>>n;
    //构造素数表
    memset(is_z,true,sizeof(is_z));
    for(int i=2;i<=sqrt(n*3);i++){
        if(is_z[i]==false)continue;
        for(int j=2;j*i<=n*3;j++)is_z[i*j]=false;
    }
    for(int i=2;i<=n;i++)if(is_z[i]==true)zsb[cur++]=i;
    //dfs
    for(int i=0;i<cur;i++){
        dfs(0,3,0);  //dfs(now,已经选了几个数,summary)
    }
    for(int i=0;i<3;i++){cout<<ans.top()<<" ";ans.pop();}
    return 0;
}

by liukairui @ 2019-07-12 14:48:26

@海阔天空818