| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 4877 | Qwaz | 파일 삭제 (GA3_delete) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}