답안 #4877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4877	2014-01-06T08:46:23 Z	Qwaz	파일 삭제 (GA3_delete)	C++	컴파일 오류	0 ms	0 KB

delete

#include <cstdio>
#include <vector>

using namespace std;
const int MAX=3020, MAX_N=10020, INF=MAX_N;

int n, m, target, p[MAX], cnt[MAX];
vector < int > children[MAX];

void input(){
	scanf("%d%d%d", &n, &m, &target);

	int i;
	for(i=0; i<n; i++){
		int t;
		scanf("%d", &t);
		cnt[t]++;
	}

	for(i=0; i<m; i++){
		scanf("%d", &p[i]);
		if(i > 0) children[p[i]].push_back(i);
	}
}

int s[MAX], e[MAX], endNum[MAX], index=1;

void numbering(int now){
	s[now] = index;

	int i;
	for(i=0; i<children[now].size(); i++){
		numbering(children[now][i]);
		cnt[now] += cnt[children[now][i]];
	}

	e[now] = index;
	endNum[index] = now;
	index++;
}

int dp[MAX][MAX_N];

void solve(){
	numbering(0);

	int i, j;
	for(i=1; i<=target; i++)
		dp[0][i] = INF;

	for(i=1; i<index; i++){
		int now = endNum[i];
		for(j=0; j<=target; j++){
			dp[i][j] = dp[i-1][j];
			if(j >= cnt[now] && dp[i][j] > dp[s[now]-1][j-cnt[now]]+1)
				dp[i][j] = dp[s[now]-1][j-cnt[now]]+1;
		}
	}

	int res=INF;
	for(i=0; i<=target; i++)
		res = min(res, dp[index-1][i]+(target-i));

	printf("%d\n", res);
}

int main(){
	input();

	solve();

	return 0;
}

Compilation message

delete.cpp: In function 'void numbering(int)':
delete.cpp:32:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
delete.cpp: In function 'void input()':
delete.cpp:11:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
delete.cpp:16:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
delete.cpp:21:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
/tmp/ccU32z2y.o: In function `main':
delete.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccmChtZt.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccmChtZt.o: In function `main':
grader.cpp:(.text.startup+0xf4): undefined reference to `DeletePlan(int, int, int, int*, int*)'
collect2: ld returned 1 exit status