JLOI2010 世界杯租房

数据很水,偷偷看了下好像 T \leqslant 100

嗯,DP+输出方案。记得为了字典序最小我们要倒着DP。。

然后没了。。别写龊了写炸复杂度就好。

O(Tmn^2)

 

 

#洛谷 P1026 统计单词个数

垃圾题……照样处理一发区间[i,j]有多少单词然后枚举区间起点i转移就行了。

 

题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入输出格式

输入格式:

每组的第一行有二个正整数(p,k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行,每行均有20个字符。

再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)

接下来的s行,每行均有一个单词。

输出格式:

一个整数,分别对应每组测试数据的相应结果。

提供一组卡了我好久的数据,注意区间[i,j]的长度。。。

Testdata.in

10 4
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
1
aaaaa

Testdata.out

193

比分割字串稍难了一点……主要难在倒推k[i][j] ([i,j]有多少单词),写个模拟就行了吧大概……

 

USACO 3.4 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐,一首歌不能分装在两张CD中。CD数量可以用完,也可以不用完

不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择:

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注:第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

一开始我看见这道题打了一道背包……

结果很惨的GG了……

我们设f[n][m][k]表示前n首歌按顺序尽量向m张盘里装,然后附加k分钟所能装的最多歌曲数

那么,显然k<=T,因为……如果k>T那f[i][j][k]等价于f[i][j+1][k-T],所以k>T是没有意义的

我们来考虑第n首歌装到第m+1张盘里的决策,也就是转移f[n][m][k] (因为m张盘外加k分钟,如果用那k分钟,也就是向m+1张里面装)

先初始化一下,也就是尝试放弃第i首歌

如果第j+1张盘的前k分钟能装的下,

那就不装,或者用前j张和j+1张的前k-a[i]分钟装前i-1首,第j+1张的最后a[i]分钟(歌曲的长度)装第i首

这两个里面取max

如果第j+1张盘的前k分钟装不下,

那么,假如说存在第j张盘(可以有j=0而k>0,也就是装第一张),那么就不装,或者用前j-1张盘外加第j张盘的T-a[i]分钟装前i-1首,用第j张盘装第i首试一下 (那么,就相当于尽量把第i首歌往j整张盘里装,如果a[i]小于T,那一定能装上,而如果T<a[i]了,那这首歌显然只能放弃)。

我们为什么要有第二个方程?原因在于k不一定大于a[i],而如果这首歌对决策有影响,那么T一定大于a[i],所以有必要试着装一下。

那么整个方程……

然后这是代码……

IOI1997 花店橱窗布置

题目描述

某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序编号,V是花瓶的数目。花束可以移动,并且每束花用1到F的整数标识。如果I < J,则花束I必须放在花束J左边的花瓶中。例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶只能放一束花。

每个花瓶的形状和颜色也不相同,因此,当各个花瓶中放入不同的花束时,会产生不同的美学效果,并以美学值(一个整数)来表示,空置花瓶的美学值为0。在上述的例子中,花瓶与花束的不同搭配所具有的美学值,可以用如下的表格来表示:

花瓶1 花瓶2 花瓶3 花瓶4 花瓶5

杜鹃花 7 23 -5 -24 16

秋海棠 5 21 -4 10 23

康乃馨 -21 5 -4 -20 20

根据表格,杜鹃花放在花瓶2中,会显得非常好看,但若放在花瓶4中,则显得很难看。

为了取得最佳的美学效果,必须在保持花束顺序的前提下,使花的摆放取得最大的美学值,如果具有最大美学值的摆放方式不止一种,则输出任何一种方案即可。

输入格式:
输入文件的第一行是两个整数F和V,分别为花束数和花瓶数(1≤F≤100,F≤V≤100)。接下来是矩阵Aij,它有I行,每行J个整数,Aij表示花束I摆放在花瓶J中的美学值。

输出格式:
输出文件的第一行是一个整数,为最大的美学值;接下来有F行,每行两个数,为那束花放入那个花瓶的编号。

可以DP,设状态f[i][j]表示第i朵花放在j号瓶子里面的最大美学值,那么从前i-1朵花放在前i-1 ~ j-1个瓶中产生的美学值取Max转移

则有:

并且,记录i-1是放在j花瓶的状态转移来的

最后取f[flower][flower~vase],然后递归输出摆放方案就可以了

所以这道弱智DP就完成了……太简单了不好意思写题解QnQ