글 읽기 - 도와쭈세요

shinwoo080401 3년 전 0

도와주세요 고수님들 뭘더 줄여야 시간초과를 막을까요??

이게 그 겹치지 않는 n/2길이의 수열을 만든후 1~~n/2까지 그수열과 다른 수들을 모아

또다른 수열을만들고 만든 두개의 수열중 2개만 골라(서로다른)그둘을 인덱스로 하여

합을구한뒤 차를 구하여 그중 작은값을 구하는것 입니다(제 프로그램).

#include<bits/stdc++.h>
int a[1004],d[1004][1004],n,ck[104],min=99999,b[1004];
void f(int p)
{
	int x,i,j,b2=0,sum=0,sum2=0;
	if(p==n/2+1){
		for(i=1; i<=n/2; i++){
			ck[a[i]]=1;
		}
		for(i=1; i<=100; i++){
			if(ck[i]==0){
				b[++b2]=i;
			}
		}
		for(i=1; i<=100; i++)ck[i]=0;
		for(i=1; i<=n/2; i++){
			for(j=1; j<=n/2; j++){
				if(a[i]!=a[j]){
					sum+=d[a[i]][a[j]];
				}
				if(b[i]!=b[j]){
					sum2+=d[b[i]][b[j]];
				}
			}
		}
			
		int k=abs(sum-sum2);
		if(min>k)min=k;
		return ;
	}
	for(i=1; i<=n; i++){
		x=0;
		a[p]=i;
		for(j=1; j<p; j++){
			if(a[j]==a[p])x=1;
		}
		if(x==1){
			a[p]=0;
			continue;
		}
		else f(p+1);
	}
}
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			scanf("%d",&d[i][j]);
		}
	}
	f(1);
	printf("%d\n",min);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와쭈세요

shinwoo080401 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말