TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose

水题，就是一个暴力。大力出奇迹。

Problem Statement

There is a narrow passage. Inside the passage there are some wolves. You are given a vector size that contains the sizes of those wolves, from left to right.


The passage is so narrow that some pairs of wolves cannot pass by each other. More precisely, two adjacent wolves may swap places if and only if the sum of their sizes is maxSizeSum or less. Assuming that no wolves leave the passage, what is the number of different permutations of wolves in the passage? Note that two wolves are considered different even if they have the same size.


Compute and return the number of permutations of wolves that can be obtained from their initial order by swapping a pair of wolves zero or more times.

Definition

Class: NarrowPassage2Easy Method: count Parameters: vector , int Returns: int Method signature: int count(vector size, int maxSizeSum) (be sure your method is public)

Limits

Time limit (s): 2.000 Memory limit (MB): 256

Constraints

- size will contain between 1 and 6 elements, inclusive. - Each element in size will be between 1 and 1,000, inclusive. - maxSizeSum will be between 1 and 1,000, inclusive.

Examples

0)

{1, 2, 3} 

Returns: 2 

From {1, 2, 3}, you can swap 1 and 2 to get {2, 1, 3}. But you can't get other permutations. 1)

{1, 2, 3} 

1000 

Returns: 6 

Here you can swap any two adjacent wolves. Thus, all 3! = 6 permutations are possible. 2)

{1, 2, 3} 

Returns: 3 

You can get {1, 2, 3}, {2, 1, 3} and {2, 3, 1}. 3)

{1,1,1,1,1,1} 

Returns: 720 

All of these wolves are different, even though their sizes are the same. Thus, there are 6! different permutations possible. 4)

{2,4,6,1,3,5} 

Returns: 60 

5)

{1000} 

1000 

Returns: 1 

#include #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #define eps 1e-10///#define M 1000100///#define LL __int64#define LL long long#define INF 0x7fffffff#define PI 3.1415926535898#define zero(x) ((fabs(x)  size, int maxSizeSum)    {        int len = size.size();        memset(vis, 0, sizeof(vis));        for(int i = 1; i   maxSizeSum)                {                    ///vis[i][j] = 1;                    vis[j][i] = 1;                }            }        }        for(int i = 1; i   maxSizeSum) return 1;            return 2;        }        if(len == 3)        {            for(int i = 1; i   f;    f.push_back(189);    f.push_back(266);    cout<

      
查看更多关于TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose的详细内容...
        

          
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did106112