bzoj1812 [Ioi2005]rivBZOJ1812: [Ioi2005]riv

riv

差一点全Byteland王国都于林海及河水所掩盖。小点的江湖汇聚到一块儿,形成了稍大点的河里。就这样,所有的江河都围拢并流进了一致漫漫大河,最后就长长的大河流进了深海。这漫长大河的入海口处发生一个聚落——名叫Bytetown
于Byteland国,有n个伐木的山村,这些村子还所获于河边。目前于Bytetown,有一个宏大的伐木场,它处理着全国砍下的备木料。木料为斩下后,顺着水而受以至Bytetown的伐木场。Byteland的国君决定,为了减少运输木材的费,再额外地建造k个伐木场。这k个伐木场将让盖在外村庄里。这些伐木场建造后,木料就无须还于送及Bytetown了,它们得以在
运输过程遭到第一只碰到的新伐木场被拍卖。显然,如果伐木场座落的酷村子就毫无再付出运送木料的支出了。它们可一直给本村的伐木场处理。
注意:所有的长河都无见面分开,也就是说,每一个村落,顺流而下还只有发雷同漫漫路——到bytetown。
国王的重臣计算起了每个村子每年要下多少木料,你的天职是决定以哪村子建设伐木场能收获最小之运费。其中运费的精打细算方式为:每一样块木料每本米1分钱。
编一个主次:
1.从文本读入村子的个数,另外如建设的伐木场的数额,每年每个村庄产之木头的块数以及河流之描述。
2.计算最小的运费并出口。Input第一行 包括个别独数
n(2<=n<=100),k(1<=k<=50,且
k<=n)。n为村庄数,k为要建的伐木场的多寡。除了bytetown外,每个村庄依次为取名为1,2,3……n,bytetown被命名为0。
接下来n行,每行包涵3只整数 wi——每年i村子产的木材的片数
(0<=wi<=10000)
vi——离i村子下游最近底村子(或bytetown)(0<=vi<=n)
di——vi到i的相距(km)。(1<=di<=10000)
保证每年有的木材流到bytetown的运费不超2000,000,000分
50%的数量中n不跳20。Output输出最小花费,精确到分。Sample Input

4 2
1 0 1
1 1 10
10 2 5
1 2 3 

Sample Output

4

lovebet 1

题解:

先搞出g[i][j]表示i到j的运载消费,只是单个点,将f[i][i][0]先期拍卖好,这个理应比便于吧,

还有处理处f[i][fa[i]][0]的起值,每一个父亲,就是整治漫长链上所有爸爸,什么意思,就是

一样交汇一重叠更新上。

拍卖出来的作为树形dp的初始化,然后便是dp

h1[k]表示在该点,建k个,该点建,的极致小花费。

h2[k]意味着在该点,建k个,该点未盖,最小花费。

然后便dp在哪个子孙建多少只,的一个背包dp。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #define N 107
 8 #define M 57
 9 using namespace std;
10 
11 int n,k;
12 int cnt,head[N],next[N*2],rea[N*2];
13 int fa[N],w[N],di[N],g[N][N];
14 int f[N][N][M];
15 bool vis[N][N][M];
16 
17 void add(int u,int v){next[++cnt]=head[u],head[u]=cnt,rea[cnt]=v;}
18 void dfs_init(int u)
19 {
20     int t=u;
21     while(fa[t]>=0)
22     {
23         g[u][fa[t]]=g[u][t]+w[u]*di[t];
24         t=fa[t];
25     }
26     t=u;
27     for (int i=head[u];i!=-1;i=next[i])
28     {
29         int v=rea[i];
30         dfs_init(v);
31         w[u]+=w[v];
32         f[u][u][0]+=f[v][u][0];
33     }
34     vis[u][t][0]=1;
35     while(fa[t]>=0)
36     {
37         vis[u][fa[t]][0]=1;
38         f[u][fa[t]][0]=f[u][t][0]+w[u]*di[t];
39         t=fa[t];
40     }
41 }
42 int solve_dp(int u,int now,int k)
43 {
44     if (vis[u][now][k]) return f[u][now][k];
45     vis[u][now][k]=1;
46     int h1[55],h2[55];
47     memset(h1,0,sizeof(h1));
48     for (int i=0;i<=k;i++)
49         h2[i]=g[u][now];
50     for (int i=head[u];i!=-1;i=next[i])
51     {
52         int v=rea[i];
53         for (int j=k;j>=0;j--)
54         {
55             h1[j]+=solve_dp(v,u,0);
56             h2[j]+=solve_dp(v,now,0);
57             for (int t=1;t<=j;t++)
58             {
59                 h1[j]=min(h1[j],h1[j-t]+solve_dp(v,u,t));
60                 h2[j]=min(h2[j],h2[j-t]+solve_dp(v,now,t)); 
61             }
62         }
63     }
64     f[u][now][k]=min(h1[k-1],h2[k]);
65     return f[u][now][k];  
66 }
67 int main()
68 {
69     memset(head,-1,sizeof(head));
70     scanf("%d%d",&n,&k);
71     for (int i=1;i<=n;i++)
72     {
73         scanf("%d%d%d",&w[i],&fa[i],&di[i]);
74         add(fa[i],i);
75     }
76     fa[0]=-1;
77     dfs_init(0);
78     printf("%d\n",solve_dp(0,0,k));
79 }

 

1812: [Ioi2005]riv

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 523  Solved: 309
[Submit][Status][Discuss]

Description

差一点
乎整个Byteland王国都深受林海及水流所挂。小点的川汇聚到一头,形成了稍大点的水。就如此,所有的河流都凑合并流进了同等修大河,最后这长达大河流进
了深海。这长达大河的入海口处发生一个村——名叫Bytetown
在Byteland国,有n个伐木的庄,这些村还所获于河边。目前以Bytetown,有一个伟人的伐木场,它处理在全国砍下之拥有木料。木料为剁下
后,顺着河水而深受应用到Bytetown的伐木场。Byteland的国王决定,为了削减运输木材的开支,再额外地建造k个伐木场。这k个伐木场将受盘在该
他村庄里。这些伐木场建造后,木料就无须都被送及Bytetown了,它们得以当
运输过程遭到第一个碰到的新伐木场被拍卖。显然,如果伐木场座落的非常村子虽甭还交由运送木料的开支了。它们可以一直为本村的伐木场处理。
注意:所有的河都非会见分,也就是说,每一个农庄,顺流而下还不过来同漫长总长——到bytetown。
国王的鼎计算出了每个村子每年使下多少木料,你的天职是决定于怎样村子建设伐木场能博得最好小之运费。其中运费的乘除办法为:每一样块木料每本米1区划钱。
编一个序:
1.打文本读入村子的个数,另外如建设的伐木场的数,每年每个村子产之木材的块数以及水的讲述。
2.计量最小之运费并出口。

Input

第一行 包括个别独数 n(2<=n<=100),k(1<=k<=50,且
k<=n)。n为村庄数,k为要建的伐木场的多少。除了bytetown外,每个村庄依次被命名吧1,2,3……n,bytetown被取名为0。
接下来n行,每行包涵3单整数 wi——每年i村子产的木的丘数
(0<=wi<=10000)
vi——离i村子下游最近之村子(或bytetown)(0<=vi<=n)
di——vi到i的相距(km)。(1<=di<=10000)
保证每年有的木流到bytetown的运费不超2000,000,000分
50%的数据中n不跳20。

Output

输出最小花费,精确到分。

Sample Input

4 2
1 0 1
1 1 10
10 2 5
1 2 3

Sample Output

4

HINT

Source

【题解】

预先左耳子右兄弟转二立交树,方便转移

f[i][j][k]表示在原树中i和i的弟兄节点所在的子树(相当给易后i及其子树中),在原树中离i最近的阿爸点吗j,

放置k个工厂的不过小离

转移:

f[i][j][k]
= min{

选      
f[l[i]][i][a] + f[r[i]][j][k – a – 1]

不选
d[l[i]][j][a] + f[r[i]][j][k – a] + dist[i,
j]

}

lovebet 2lovebet 3

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath> 
 6 #include <algorithm>
 7 #define min(a, b) ((a) < (b) ? (a) : (b))
 8 #define max(a, b) ((a) > (b) ? (a) : (b))
 9  
10 inline void read(int &x)
11 {
12     x = 0;char ch = getchar(), c = ch;
13     while(ch < '0' || ch > '9')c = ch, ch = getchar();
14     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
15     if(c == '-')x = -x;
16 }
17  
18 const int MAXN = 100 + 10;
19 const int MAXK = 50 + 10;
20 int dp[MAXN][MAXN][MAXK],n,m,cost[MAXN],fa[MAXN],dist[MAXN];
21 int l[MAXN], r[MAXN], flag;
22  
23 void dfs(int i)
24 {
25     if(!i && flag)return;
26     flag = 1;
27     dfs(l[i]);
28     dfs(r[i]);
29     int len = dist[i];
30     for(register int j = fa[i];j != -1;j = fa[j])
31     {
32         for(register int k = 0;k <= m;++ k)
33         {
34             for(register int a = 0;a <= k;++ a)
35             {
36                 if(k - a - 1 >= 0)
37                     dp[i][j][k] = min(dp[i][j][k], dp[l[i]][i][a] + dp[r[i]][j][k - a - 1]);
38                 if(k - a >= 0)
39                     dp[i][j][k] = min(dp[i][j][k], dp[l[i]][j][a] + dp[r[i]][j][k - a] + len * cost[i]);
40             }
41         }
42         len += dist[j]; 
43     } 
44 }
45  
46 int main()
47 {
48     read(n), read(m);
49     for(register int i = 1;i <= n;++ i)
50     {
51         read(cost[i]), read(fa[i]),read(dist[i]);  
52         r[i] = l[fa[i]];
53         l[fa[i]] = i;       
54     }
55     memset(dp, 0x3f, sizeof(dp));
56     memset(dp[0], 0, sizeof(dp[0]));
57     fa[0] = -1;
58     dfs(0); 
59     printf("%d", dp[l[0]][0][m]);
60     return 0;
61 }

BZOJ1812

 

相关文章