Heim > Web-Frontend > HTML-Tutorial > Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose

Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose

WBOY
Freigeben: 2016-06-24 11:54:56
Original
1120 Leute haben es durchsucht

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

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}
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Returns: 2
Nach dem Login kopieren
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}
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
1000
Nach dem Login kopieren
Nach dem Login kopieren
Returns: 6
Nach dem Login kopieren
Here you can swap any two adjacent wolves. Thus, all 3! = 6 permutations are possible.
2)  
 
{1, 2, 3}
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren
Returns: 3
Nach dem Login kopieren
You can get {1, 2, 3}, {2, 1, 3} and {2, 3, 1}.
3)  
 
{1,1,1,1,1,1}
Nach dem Login kopieren
Returns: 720
Nach dem Login kopieren
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}
Nach dem Login kopieren
Returns: 60
Nach dem Login kopieren
5)  
 
{1000}
Nach dem Login kopieren
1000
Nach dem Login kopieren
Nach dem Login kopieren
Returns: 1
Nach dem Login kopieren
#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <stack>#include <map>#include <set>#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)<eps namespace std int maxn="1000010;int" vis narrowpassage2easy count> 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  <br>  <br>  <p></p> </eps></set></map></stack></cmath></queue></string></stdio.h></iomanip></string.h></stdlib.h></iostream></algorithm>
Nach dem Login kopieren
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage