차례로 검색 nyoj 325 nyoj 32

2559 단어
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, r,ans[100];
void dfs(int u,int step)
{
	if (u <= 0)return;
	if (step == r)
	{
		for (int i = 1; i < r; i++)
			printf("%d", ans[i]);
		printf("%d
",u); return; } else { ans[step] = u; for (int i = 1;i<=n;i++) dfs(u - i, step + 1); } } int main() { while (~scanf("%d%d", &n, &r)) { for (int i = n; i >= r; i--) { dfs(i,1); } } return 0; }

조합수


시간 제한:
3000ms | 메모리 제한:
65535 KB
난이도:

묘사
자연수 1, 2,...n(0입력
n, r를 입력합니다.
출력
모든 조합을 특정 순서대로 출력합니다.
특정 순서: 모든 조합의 값은 큰 것부터 작은 것까지 배열되고, 조합 사이에는 역사전순으로 배열된다.
샘플 입력
5 3

샘플 출력
543
542
541
532
531
521
432
431
421
321

출처
[묘동동] 오리지널.
업로드
묘동
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int n,a[1000],sum,ans;
void dfs(int u,int pos)
{
	ans = min(ans, abs(sum - 2*u));
	if (pos == n)return;
	dfs(u + a[pos], pos + 1);
	dfs(u, pos + 1);
	
}
int main()
{
	while (~scanf("%d", &n))
	{
		ans = inf;
		sum = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", a + i);
			sum += a[i];
		}
		dfs(0,1);
		printf("%d
", ans); } return 0; }

생일


시간 제한:
3000ms | 메모리 제한:
65535 KB
난이도:

묘사
오늘은 음력 7월 5일, acm대원zb의 생일입니다.zb는 C소가, 네버와 무한에서 훈련을 하고 있다.그는 이 두 형제에게 생일을 축하하는 것을 사주고 싶었다. 조사를 통해 zb는 C소가와 네버가 모두 수박을 즐겨 먹는 것을 발견했다. 그리고 먹으면 한 무더기인 것을 발견했다. zb는 즉시 결심하고 수박 한 무더기를 샀다.그가 수박을 C소가와 네버에게 주려고 할 때 어려운 문제에 부딪혔다. 네버와 C소가는 함께 살지 않고 수박을 두 무더기로 나누어 그들에게 줄 수밖에 없었다. 모든 사람에게 공평하기 위해 그는 두 무더기의 무게 차이를 최소화하려고 했다.모든 수박의 무게는 이미 알고 있는데, 네가 그를 좀 도와줄 수 있니?
입력
다중 테스트 데이터(<=1500).데이터는 EOF로 끝납니다.
첫 줄 입력 수박 수량 N(1≤N≤20)
두 번째 줄은 N개수, W1,...Wn(1≤Wi≤10000)이 각각 수박의 무게를 대표한다
출력
출력을 두 무더기로 나눈 후의 품질 차이
샘플 입력
5
5 8 13 27 14

샘플 출력
3

출처
ural
업로드
이문흠
이 문제는 0-1 가방으로 풀 수도 있고 검색 트리를 하나씩 만들 수도 있습니다. 검색 시간의 복잡도는 2^n입니다.

좋은 웹페이지 즐겨찾기