一道显而易见的树形 dp
每个人都有当根节点的机会
然后先告诉需要花费时间长的, 再告诉短的
转移方程
- dp[u]=max(dp[u],dp[v]+i?1)
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define maxn 1010
- #define INF 999999999
- int n;
- int dp[maxn];
- int head[maxn],cnt;
- int www[maxn],minn = INF;
- struct EDGE {
- int nxt,to;
- } edge[maxn * 2];
- int cmp(int a,int b) {
- return a> b;
- }
- void add(int x,int y) {
- edge[++cnt].to = y;
- edge[cnt].nxt = head[x];
- head[x] = cnt;
- }
- void dfs(int u,int fa) {
- int son[maxn] = {0};
- int total = 0;
- for(int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if(v != fa) {
- dfs(v,u);
- son[++total] = dp[v];
- }
- }
- sort(son + 1,son + total + 1,cmp);// 先传给花时间长的
- for(int i = 1; i <= total; i++)
- dp[u] = max(dp[u],son[i] + i - 1);// 转移方程, 儿子到根节点的距离 i 再减 1
- dp[u] += 1;
- }
- int main() {
- scanf("%d",&n);
- for(int i = 2; i <= n; i++) {
- int a;
- scanf("%d",&a);
- add(a,i);
- add(i,a);
- }
- for(int i = 1; i <= n; i++) {// 每个点都当一遍根节点
- memset(dp,0,sizeof(dp));// 别忘了每次清零
- dfs(i,0);
minn = min(minn,dp[i]); 存最小值
www[i] = dp[i];// 记录每次的值 } printf("%d\n",minn); for(int i = 1; i <= n; i++) if(minn == www[i]) printf("%d",i); return 0; }
集训回来, 从今天开始疯狂补博客了
做了蛮多题, 都想写写题解加深印象, 希望不会鸽
来源: http://www.bubuko.com/infodetail-2944758.html