imported>miura0806 at 12:55, 22 September 2014

2014-09-22T12:55:03Z

New page

[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=595&page=show_problem&problem=4548]

== 최다인 ==
재귀함수로 짰더니 타임오버... ^_ㅠ
하... 죽겠다...
#include <stdio.h>

long long output = 0;
int outputcase[101];
void foo(int);
void foo2(int, int, int*, int*);

int main() {
int T, n, k;
int a[100];

scanf("%d", &T);
for (int i = 0; i < T; i++) {
output = 0;
foo(i);
}
for (int i = 0; i < T; i++) {
printf("Case #%d: %d\n", i + 1, outputcase[i + 1]);
}
}

void foo(int casenum) {
int n, k;
int a[101], temp[101];

scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++) {
scanf("%d", &a[i]);
}

/* 초기화 */
for (int i = 1; i <= n; i++) {
temp[i] = 0;
}
for (int i = 1; i <= k; i++) {
temp[a[i]] = 1;
}

foo2(n, k + 1, a, temp);

outputcase[casenum + 1] = output;
}

void foo2(int n, int i, int a[101], int temp[101]) {
if (i == n + 1) {
int p = 0, g = 0;
int b[101];

for (int j = 1; j <= n; j++) {
b[j] = a[j];
}
for (int j = 1; j <= n; j++) {
if (j - b[j] > 0) {
g += (j - b[j]);
}
}
for (int j = 0; j < n - 1; j++) {
for (int k = 1; k <= n - 1 - j; k++) {
if (b[k] > b[k + 1]) {
int temp = b[k];
b[k] = b[k + 1];
b[k + 1] = temp;
p++;
}
}
}
if (p == g) {
output++;
if (output == 1000000007) {
output = 0;
}
}

}
for (int j = 1; j <= n; j++) {
if (temp[j] == 1) { continue; }
a[i] = j;
temp[j] = 1;
foo2(n, i+1, a, temp);
temp[j] = 0;
}
}

ACM ICPC/Problems/6537 - Revision history

imported>miura0806 at 12:55, 22 September 2014