TopCoder SRM 638 Div2 NarrowPassage2Easy

題目鏈接:http://community.topcoder.com/stat?c=problem_statement&pm=13520&rd=16081

題意

有n個數字,和一個maxSizeSum,當相鄰連個數字滿足

• size[i]+size[i+1]<=maxSizeSum (0<=i<n-1)

求滿足條件的排列總數

解法

由於數據量很小,所以直接暴力
先枚舉出來排列,然後判斷是否滿足條件,統計即可

class NarrowPassage2Easy {
  public:
    vector<int> sz;
    int maxsz;
    int res;
    int n;
    bool use[10];
    int id[10];
    void dfs(int index) {
        if(index>=n) {
            bool flag=0;
            for(int i=0;i<n-1;i++) {
                for(int j=i+1;j<n;j++) {
                    if(id[i]>id[j]) {
                        if(sz[id[i]]+sz[id[j]]>maxsz) {
                            flag=1;
                            break;
                        }
                    }
                }
                if(flag) break;
            }
            if(!flag) res++;
            return;
        }
        for(int i=0;i<n;i++) {
            if(use[i]) continue;
            use[i]=1;
            id[index]=i;
            dfs(index+1);
            use[i]=0;
        }
    }
    int count(vector <int> size, int maxSizeSum) {
        sz=size;
        memset(use,0,sizeof(use));
        maxsz=maxSizeSum;
        n=size.size();
        res=0;
        dfs(0);
        return res;
    }
};