2010-1111

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

'''题目描述：'''
[[BR]]
题目背景很邪恶。
[[BR]]
有个姑娘会在zjg待d天，在这d-1个晚上里，她会睡在zjg的寝室里面。
[[BR]]
总共有n间不同的寝室，每间寝室的同学会按照她在该寝室睡觉连续的天数来支付不同的金额。第i间寝室一天 a[ i ][ 1 ] 元，两天 a[ i ][ 2 ] 元，三天或以上 a[ i ][ 3 ] 元。
[[BR]]
为了多赚钱，这位姑娘可以在寝室直接自由搬迁，但要支付给原宿舍的同学一定的分手费。从 x 寝室搬到 y 寝室需要bg[ x ][ y ]的费用，而且有的寝室他还不一定让你搬过去。
[[BR]]
一天可以搬迁任意多次，并且一旦搬出她在原寝室的连续睡觉天数将会清零。
[[BR]]
问最多可以赚多少钱。

[[BR]]
'''解题方法：'''
[[BR]]
动态规划
[[BR]]
用数组bg[x][y]表示在一天当中从 x 寝室搬到 y 寝室所需要的分手费的最小值。可以用Floyd算法求之。
[[BR]]
然后就可以开始Dp了
[[BR]]
f[l][j][k]表示在第l天，她在j寝室已经连续睡了k天时能赚到的最大钱数。
[[BR]]
有3个状态方程
[[BR]]

{{{
f[l][j][1] = max { f[l-1][k][i] - bg[k][j] + a[j][1] | 0 < k <= n  并且 f[l-1][k][i] - bg[k][j] > 0 }
f[1][j][2] = f[l-1][j][1] + a[j][2];
f[1][j][3] = max { f[l-1][j][2] , f[l-1][j][3] }
}}}

[[BR]]
最后就在
[[BR]]
f [ d - 1 ][ i ][ j ]找最大值

题目描述：

题目背景很邪恶。

有个姑娘会在zjg待d天，在这d-1个晚上里，她会睡在zjg的寝室里面。

总共有n间不同的寝室，每间寝室的同学会按照她在该寝室睡觉连续的天数来支付不同的金额。第i间寝室一天 a[ i ][ 1 ] 元，两天 a[ i ][ 2 ] 元，三天或以上 a[ i ][ 3 ] 元。

为了多赚钱，这位姑娘可以在寝室直接自由搬迁，但要支付给原宿舍的同学一定的分手费。从 x 寝室搬到 y 寝室需要bg[ x ][ y ]的费用，而且有的寝室他还不一定让你搬过去。

一天可以搬迁任意多次，并且一旦搬出她在原寝室的连续睡觉天数将会清零。

问最多可以赚多少钱。

解题方法：

动态规划

用数组bg[x][y]表示在一天当中从 x 寝室搬到 y 寝室所需要的分手费的最小值。可以用Floyd算法求之。

然后就可以开始Dp了

f[l][j][k]表示在第l天，她在j寝室已经连续睡了k天时能赚到的最大钱数。

有3个状态方程

f[l][j][1] = max { f[l-1][k][i] - bg[k][j] + a[j][1] | 0 < k <= n  并且 f[l-1][k][i] - bg[k][j] > 0 }
f[1][j][2] = f[l-1][j][1] + a[j][2];
f[1][j][3] = max { f[l-1][j][2] , f[l-1][j][3] }

最后就在

f [ d - 1 ][ i ][ j ]找最大值