Tinux系统[HNOI2002]

AK-dream

发布于：2019年9月25日

次浏览

【题目描述】
原题又臭又长 不写了 请自行去看题面
大意：一棵有根树 每一个节点最多只能有$k$个子节点 要放$n$个文件进去 文件只能放在叶子节点里 从任意一个非叶子节点（文件夹）访问到他的第$i$个子节点需要耗费时间$p_i$访问一个文件的时间定义为从根节点访问到该文件所处的叶子节点所需时间 求一种文件放置方法 使得依次访问每个文件花费的时间总和最小

【输入格式】
文件的第一行为两个正整数$N,K$($1 \le N \le 1000, 2 \le K \le 150$)接下来的$K$行每行有一个正整数$P_i, P_i \le150$。

【输出格式】
在最优存储方案下的时间总和

这题在某谷上是黑题
黑题我怎么会做呢 网上搜了一下题解的思路然后胡搞搞过了就来写Blog

首先 由于对于一个非叶子节点我们可以随便选择优先用哪个子节点 所以肯定从时间花费少的用起 所以可以先给$p$数组排序

然后此题我们可以用记忆化搜索求解实际上就是DP 设$f[i][j]$表示 还剩$i$个文件需要安排 使用第$j$个子节点到第$k$(如果忘了$k$是什么 回去读题)个子节点(排序后的) 最优安排方案下访问这$i$个点所需的最短时间

转移 对于$dp[i][j]$如果$i=1$就直接把这个文件扔当前这个第$j$个子节点就行了
如果$j=1$且$i>1$那就必须在第$j$个子节点这个位置新开一个文件夹了 耗费时间就是$dp[i][1]$(新文件夹从子节点1开始)$+p[i]*i*i$$p[i]*i*i$就是把这$i$个文件经过这里所需的时间给提前算进去了
对于其它情况 枚举$x$表示要放在当前的第$j$个子节点的位置或者$j$位置下面的文件夹的文件个数$dp[i][j] = min(dp[x][1]+dp[i-x][j+1]+p[i]*x*x)$;

DP时可以使用一种dfs的方法

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, k, p[1005];
ll dp[1005][205];

int dfs(ll need, ll cur) {
    if (need == 1) {
        return dp[need][cur] = p[cur];
    } else if (cur == k) {
        return dp[need][cur] = p[cur] * need * need + dfs(need, 1);
    }
    if (dp[need][cur]) return dp[need][cur];
    dp[need][cur] = p[cur] + dfs(need - 1, cur + 1);
    for (int i = 2; i < need; i++) {
        dp[need][cur] = min(dp[need][cur], dfs(need - i, cur + 1) + dfs(i, 1) + p[cur] * i * i);
    }
    return dp[need][cur];
}

int main() {
    scanf("%lld %lld", &n, &k);
    for (int i = 1; i <= k; i++) {
        scanf("%lld", &p[i]);
    }
    sort(p + 1, p + k + 1);
    printf("%lld\n", dfs(n, 1));
    return 0;
}

众所周知 黑题的代码量很小

更新于：2020年9月7日

动态规划