【NOIP模拟赛】机房人民大团结

2014年11月2日1,1820

最近,机房出了一个不团结分子:Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”,使同学们神志不清,殴打他人,砸烂计算机,破坏机房团结。幸运地,一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起,共同对抗Dr.Weissman及“教授糖豆”。

同学们十分具有社会责任感:他们害怕“教授糖豆”流向社会,导致动乱。于是,刚才提到的和谐家身先士卒,为了实验,品尝“教授糖豆”。

每个“教授糖豆”的性质都有所不同。同志们已经研究出每个糖豆对人的影响。具体地,每个糖豆都有一个破坏值,吃掉这颗糖豆后,身先士卒的和谐家会对机房造成一定的破坏,破坏程度为先前累积的破坏值加上本次食用糖豆的破坏值,而且这颗“教授糖豆”的破坏值会加入累积。为了减小实验造成的破坏,同学们准备了几颗“治疗糖豆“,功能是无条件将累积的“破坏值”清零。

由于实验要求,和谐家只能按照给定的顺序吃掉“教授糖豆”,但可以随时吃掉一颗或多颗“治疗糖豆”。

你能帮助和谐家同志尽量减小实验所造成的破坏吗?

【输入】

第一行,两个数,用空格,分隔开,一个n,一个m。(n,m均为正整数。)n表示“教授糖豆”的数目,m表示“治疗糖豆”的数目。

剩余n行,每行1个正整数,表示“教授糖豆”的破坏值。和谐家必须按照给定的顺序,一次一个,吃掉所有“教授糖豆”。

【输出】

一行,一个数,表示实验造成的最小破坏。

【输入样例】

3 1

1 2 3

【输出样例】

7

【数据规模】

对于100%的数据,1<=n<=100,m<=n

所有破坏值的加和小于10^9。

题解

显然二分是不可以的

应该用dp来做

f[i][j][k]表示吃了i个糖,j个药,最后一个药在吃k个糖前吃了的最小代价

转移比较简单

或者用f[i][j]表示吃了i个糖j个药,然后把药看成在糖的序列中放一些断点,预处理一下吃一段糖的代价

这个似乎更好想