這個題bzoj上沒有圖，luogu上樣例有問題。。。其實這個題代碼不難，但是思考起來還是有一定難度的，其實這些題的重點都在于思考。我就不寫了，洛谷上唯一的題解寫的挺好，大家可以看一看。

題干：

在dos系統誕生以前，美國曾研究出一種類似的操作系統，名為Tinux系統。但由于硬件設施的制約，Tinux系統有許多的缺點。下面就對Tinux系統作一個簡單的介紹：

Tinux系統是Tiger博士為美國軍方研制開發的一種操作系統，該系統對文件的存儲方式類似于dos系統，像一棵樹一樣，每一個葉子節點表示一個文件，每一個非葉子節點表示一個目錄。其中定義i級子目錄表示從根目錄開始訪問，一直訪問到該子目錄（不包括該子目錄）需要訪問的目錄的個數為i的目錄，所以根目錄下的目錄為一級子目錄，其他的目錄以此類推。但是在同一子目錄下，受到硬件的制約Tinux系統最多只能夠存儲k個文件或子目錄，也就是說這棵樹里面的每一個非葉子節點最多只有k個子節點。這樣就導致在文件數量較多的情況下，訪問存儲在該系統當中的文件A，往往要先訪問一系列的子目錄，我們稱這些子目錄為文件A的上級目錄。例如下面這一個例子：

Root ? A1

? A2

? A3

? A4

? A4A1

? A4A2

? A4A2A1

? A4A2A2

? A4A3

當我們要訪問文件A4A2A1時就必須先訪問它的上級目錄：一級子目錄A4和二級子目錄A4A2。

Tinux系統在存儲文件時，給每一個子目錄都分配了k個指針，分別指向存放在該目錄下的每一個文件和每一個目錄，因此對文件的訪問實質上就是對指針的訪問。但是由于硬件原因，這k個指針不盡相同，因此訪問它們的時間也不同，訪問第i個指針所耗費的時間為 。但是對于兩個不同的子目錄（不管它們各自屬于哪一級目錄）而言它們各自所擁有的k個指針是相同的。

Tinux系統最大的缺點是訪問一個目錄時，必須把該目錄下所有的文件讀入到內存當中來，這些文件包括在其各級子目錄當中的文件，例如上面那一個例子，訪問A4那一個目錄，就必須把A4A1，A4A2A1，A4A2A2，A4A3這四個文件都讀入到內存當中來，訪問一個目錄所需要的時間為 （x表示該目錄及其各級子目錄下文件的個數， 表示指向該目錄的指針的訪問時間）。因此根據上面介紹的訪問方法，單獨訪問一個文件所需要的總時間為訪問其所有上級目錄（不包括根目錄）所需要的時間與訪問指向該文件的指針所需要的時間的和，例如上面那一個例子，訪問文件A4A2A1需要的時間=訪問目錄A4的時間+訪問目錄A4A2的時間+訪問指向文件A4A2A1的指針需要的時間。

現在，tiger博士準備將n個文件存儲到一個空的Tinux系統當中，希望你幫助他設計一個程序找到一種最優的存儲方法，使得單獨訪問這n個文件所需要的時間總和最小。

輸入輸出格式

輸入格式：

輸入由文件”system.in”讀入。

文件的第一行為兩個正整數 ， ，接下來的k行每行有一個正整數 。

輸出格式：

輸出到文件”system.out”，輸出文件僅有一個正整數，表示在最優存儲方案下，單獨訪問這n個文件所需要的時間總和。（結果小于2的31次方 ）

輸入輸出樣例

輸入樣例#1： 復制 4 3 3 5 4 4 輸出樣例#1： 復制 28

說明

代碼：

#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-') op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op) x = -x; } template <class T> void write(T x) {if(x < 0) putchar('-'), x = -x;if(x >= 10) write(x / 10);putchar('0' + x % 10); } int f[1700][1700]; int n,k,p[1700]; int MIN(int x,int y) {if(!x)return y;elsereturn min(x,y); } int dp(int x,int y,int l) {if(x == 1){f[x][y] = p[y];return f[x][y];}if(y == k){f[x][y] = p[y] * x * x + dp(x,1,x - 1);return f[x][y];}int tmp = k - y + 1;if(tmp * l < x)return INF;if(f[x][y]) return f[x][y];tmp = (x - 1) / tmp + 1;duke(i,tmp,l){if(i == 1)f[x][y] = p[y] + dp(x - 1,y + 1,x - 2);elsef[x][y] = MIN(f[x][y],dp(x - i,y + 1,x - i - 1) + dp(i,1,i - 1) + p[y] * i * i);}return f[x][y]; } int main() {read(n);read(k);duke(i,1,k)read(p[i]);sort(p + 1,p + k + 1);printf("%d\n",dp(n,1,n - 1));return 0; }

?

轉載于:https://www.cnblogs.com/DukeLv/p/9726549.html

總結

以上是生活随笔為你收集整理的B1277 [HNOI2002]Tinux系统 树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。