#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(int N, int M, int K, int *A, int *B){
n = N;
m = M;
target = K;
int i;
for(i=0; i<n; i++)
cnt[A[i]]++;
for(i=0; i<m; i++){
p[i] = B[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];
int DeletePlan(int N, int M, int K, int *A, int *B){
input(N, M, K, A, B);
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));
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 2 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 3 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 4 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 5 |
Correct |
0 ms |
119540 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 2 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 3 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 4 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 5 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 6 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 7 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 8 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 9 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 10 |
Correct |
0 ms |
119540 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 2 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
119540 KB |
Output is correct |
| 4 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 5 |
Correct |
4 ms |
119540 KB |
Output is correct |
| 6 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 7 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 8 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 9 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 10 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 11 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 12 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 13 |
Correct |
4 ms |
119540 KB |
Output is correct |
| 14 |
Correct |
8 ms |
119540 KB |
Output is correct |
| 15 |
Correct |
0 ms |
119540 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 2 |
Correct |
12 ms |
119540 KB |
Output is correct |
| 3 |
Correct |
12 ms |
119540 KB |
Output is correct |
| 4 |
Correct |
32 ms |
119540 KB |
Output is correct |
| 5 |
Correct |
8 ms |
119540 KB |
Output is correct |
| 6 |
Correct |
4 ms |
119540 KB |
Output is correct |
| 7 |
Correct |
4 ms |
119540 KB |
Output is correct |
| 8 |
Correct |
0 ms |
119540 KB |
Output is correct |
| 9 |
Correct |
16 ms |
119540 KB |
Output is correct |
| 10 |
Correct |
12 ms |
119540 KB |
Output is correct |
| 11 |
Correct |
32 ms |
119540 KB |
Output is correct |
| 12 |
Correct |
44 ms |
119540 KB |
Output is correct |
| 13 |
Correct |
28 ms |
119540 KB |
Output is correct |
| 14 |
Correct |
56 ms |
119540 KB |
Output is correct |
| 15 |
Correct |
52 ms |
119540 KB |
Output is correct |
