首页 > 代码库 > Topcoder SRM 638 DIV 2 (大力出奇迹)
Topcoder SRM 638 DIV 2 (大力出奇迹)
水题，就是一个暴力。大力出奇迹。
Problem Statement | |||||||||||||
| There is a narrow passage. Inside the passage there are some wolves. You are given a vector <int>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 ismaxSizeSum 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 | |||||||||||||
| |||||||||||||
Limits | |||||||||||||
| |||||||||||||
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) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||
#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)?0:x)
using namespace std;
const int maxn = 1000010;
int vis[10][10];
class NarrowPassage2Easy
{
public:
int count(vector <int> size, int maxSizeSum)
{
int len = size.size();
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= len; i++)
{
for(int j = i+1; j <= len; j++)
{
int x = size[i-1]+size[j-1];
if(x > maxSizeSum)
{
///vis[i][j] = 1;
vis[j][i] = 1;
}
}
}
for(int i = 1; i <= len; i++)
{
for(int j = 1; j <= len; j++)
{
cout<<vis[i][j]<<" ";
}
cout<<endl;
}
int sum = 0;
if(len == 1) return 1;
if(len == 2)
{
if(size[0]+size[1] > maxSizeSum) return 1;
return 2;
}
if(len == 3)
{
for(int i = 1; i <= len; i++)
{
for(int j = 1; j <= len; j++)
{
if(i == j) continue;
for(int k = 1; k <= len; k++)
{
if(k == i || k == j) continue;
if(vis[i][j] || vis[i][k] || vis[j][k]) continue;
sum++;
}
}
}
}
if(len == 4)
{
for(int i1 = 1; i1 <= len; i1++)
{
for(int i2= 1; i2 <= len; i2++)
{
if(i1 == i2) continue;
for(int i3 = 1; i3 <= len; i3++)
{
if(i1 == i3 || i2 == i3) continue;
for(int i4 = 1; i4 <= len; i4++)
{
if(i1 == i4 || i2 == i4 || i3 == i4) continue;
if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4]
|| vis[i2][i3] ||vis[i2][i4]
||vis[i3][i4]) continue;
sum++;
}
}
}
}
}
if(len == 5)
{
for(int i1 = 1; i1 <= len; i1++)
{
for(int i2= 1; i2 <= len; i2++)
{
if(i1 == i2) continue;
for(int i3 = 1; i3 <= len; i3++)
{
if(i1 == i3 || i2 == i3) continue;
for(int i4 = 1; i4 <= len; i4++)
{
if(i1 == i4 || i2 == i4 || i3 == i4) continue;
for(int i5 = 1; i5 <= len; i5++)
{
if(i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;
if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4] || vis[i1][i5]
|| vis[i2][i3] ||vis[i2][i4] || vis[i2][i5]
||vis[i3][i4] || vis[i3][i5]
||vis[i4][i5]) continue;
sum++;
}
}
}
}
}
}
if(len == 6)
{
for(int i1 = 1; i1 <= len; i1++)
{
for(int i2= 1; i2 <= len; i2++)
{
if(i1 == i2) continue;
for(int i3 = 1; i3 <= len; i3++)
{
if(i1 == i3 || i2 == i3) continue;
for(int i4 = 1; i4 <= len; i4++)
{
if(i1 == i4 || i2 == i4 || i3 == i4) continue;
for(int i5 = 1; i5 <= len; i5++)
{
if(i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;
for(int i6 = 1; i6 <= len; i6++)
{
if(i1 == i6 || i2 == i6 || i3 == i6 || i4 == i6 || i6 == i5) continue;
if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4] || vis[i1][i5] || vis[i1][i6]
|| vis[i2][i3] ||vis[i2][i4] || vis[i2][i5] || vis[i2][i6]
||vis[i3][i4] || vis[i3][i5] || vis[i3][i6]
||vis[i4][i5] || vis[i4][i6]
|| vis[i5][i6]) continue;
sum ++;
}
}
}
}
}
}
}
return sum;
}
};
int main()
{
NarrowPassage2Easy a;
vector<int> f;
f.push_back(189);
f.push_back(266);
cout<<a.count(f, 186)<<endl;;
return 0;
}
Topcoder SRM 638 DIV 2 (大力出奇迹)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。