stdKonjac's Blog

 要做到不可替代,就要与众不同。

【登机难度】

题目描述

Peter 是 Byteland 机场的经理。他的工作就是优化登机过程。Byteland 的飞机有 s 排,编号 1 到 s 。每排 6 个座位,标号 A 到 F 。

《【登机难度】》

有 n 个乘客,他们排成队伍,一个个登机。如果第 i 个人坐在 R排,那么他登机的难度相当于在他之前登机并且坐在第 1..Ri-1 排的人的人数。登机总难度相当于所有乘客的难度的总和。

例如,如果有 10 个乘客,并且他们的座位是 6A,4B,2E,5F,2A,3F,1C,10E,8B,5A,按排队顺序,那么他们登机的难度为0,0,0,2,0,2,0,7,7,5,总难度为 23。

为了优化登机过程,Peter 想把飞机分成 k 个区域,每个区域必须是连续的几排座位。然后登机过程就分为 k 个阶段。在每个阶段,挑出一个区域,在这个区域的乘客按照原来排队的顺序登机。

在上面的例子中,如果我们把飞机分成两块区域,5—10 排和 1—4 排。那么在第一阶段,乘客会依次坐 6A,5F,10E,8B,5A;在第二阶段,乘客会依次坐 4B,2E,2A,3F,1C。通过这样划分,登机总难度变成了 6 。

已知乘客的排队顺序,帮助 Peter 把飞机分成 k 个区域,使登机总难度最小。

输入格式

输入的第一行包括 3 个正整数 n,s,k 。
下一行包括 n个 正整数 R,每排座位最多容纳 6 个乘客。

输出格式

输出包含一个正整数,表示最小登机总难度。

样例数据 1

输入

10 12 2
6 4 2 5 2 3 1 11 8 5

输出

6

备注

【数据范围】

《【登机难度】》

 

在测试点 6-10 中,k 的取值在 [0,50] 内均匀分布。

理解一下这道题,若有两个人i,j,其中i<j并且i比j先登机,那么登机难度一定会+1,也就转化为了一个求顺序对的问题,用cost[i][j]表示第i人到第j人的登机难度,可以推知:

cost[i][j]=cost[i][j]+cost[i][j-1]+cost[i+1][j]-cost[i+1][j-1].

其实就是一个容斥原理,其中cost[i][j]是预先处理过的只有第i人和第j人的情况,剩下的相当于是处理i~j之间的人的情况,相当于是(i~j-1)的情况U(i+1~j)的情况,其中i+1~j-1重复算了一次要减掉,然后用dp[i][j]表示1~i排分成j个区域的最优解,易得转移方程式dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]),然后就做完了。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.