uva 10400 Game Show Math (填合適的運算符)

看到這種填合適的運算符之類的題目，第一感覺就是用dfs來枚舉遞歸。

但郵箱道題目算法設計裡面那麼大的數據，想到有可能會超時。

用最直白的簡單的方法dfs一遍後交上，超時。

——需要判重和邊界結束條件。

在所有能剪斷的地方痛下狠手，狂加特判+return；

然後就炒雞快了

#include
#include
#include
#define ADD 32000
using namespace std;

int arr[120], target, p;
char route[120];
bool flag, vis[102][32002*2+2];

inline bool isOk(int m, int cur)
{
    return m>=-32000&&m<=32000 && !vis[cur][m+ADD];
}

void dfs(int cur, int sum)
{
    if(flag)return ;
    if(cur==p)
    {
        if(sum==target) flag=true;
        return;
    }
    if(flag) return;

    for(int i=0; i<4; ++i)
    {
        if(i==0&&isOk(sum+arr[cur], cur))
        {
            vis[cur][sum+arr[cur]+ADD] = true;
            route[cur-1]='+';
            dfs(cur+1, sum+arr[cur]);
        }
        else if(i==1 && isOk(sum-arr[cur], cur))
        {
            vis[cur][sum-arr[cur]+ADD] = true;
            route[cur-1]='-';
            dfs(cur+1,sum-arr[cur]);
        }
        else if(i==2 && isOk(sum*arr[cur], cur))
        {
            vis[cur][sum*arr[cur]+ADD] = true;
            route[cur-1]='*';
            dfs(cur+1,sum*arr[cur]);
        }
        else if(i==3 && arr[cur]!=0 && isOk(sum/arr[cur], cur))
        {
            vis[cur][sum/arr[cur]+ADD] = true;
            route[cur-1]='/';
            dfs(cur+1,sum/arr[cur]);
        }
        if(flag)return;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&p);
        for(int i=0; i