本文主要是介绍DTOJ 4780. 病毒研究，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
病毒科学家陈博士正在带领着她的团队在研究病毒，她要研究如何降低病毒的活性。病毒的活性可以用一个整数来表示，但她不知道具体的活性是多少。
她可以执行 m + 1 m+1 m+1 种操作，对于前 m m m 种操作，第 i i i 种操作为花费 v i v_i vi 的代价使得病毒 的活性减少 w i w_i wi；第 m + 1 m+1 m+1 种操作为查看当前病毒所处的状态，不需要花费任何代价。
病毒一共有 n n n 种状态。有 n + 1 n+1 n+1 个递增的数 a 0 , a 1 , a 2 , . . . , a n a_0,a_1,a_2,...,a_n a0,a1,a2,...,an，其中 a 0 = 0 a_0=0 a0=0；若病毒的活性 x x x 满足 a i − 1 < x ≤ a i a_{i-1}<x\le a_i ai−1<x≤ai，那么这个病毒就处于状态 i i i。同时，保证病毒的活 性不会大于 a n a_n an。
她可以使用每种操作任意多次，但是她不希望病毒完全丧失活性。但是如果在使用了一个操作后，病毒的活性 ≤ 0 \le 0 ≤0 了，那研究就失败了。而病毒的活性太高时也不适合研究，只有病毒处于状态 1 1 1 时才最适合研究。
现在，她只知道病毒的活性是 [ 1 , a n ] [1,a_n] [1,an] 中的一个等概率随机的整数。她想知道，在保证病毒不会完全丧失活性的情况下，她使病毒变为状态 1 1 1 的过程中，花费代价的期望最少是多少。
可以发现答案乘 a n a_n an 一定是个整数，输出答案乘 a n a_n an 的值即可。
如果不能保证病毒不会完全丧失活性，输出 − 1 -1 −1。
| 子任务编号 | a n ≤ a_n \le an≤ | 分值 |
|---|---|---|
| 1 1 1 | 10 10 10 | 17 17 17 |
| 2 2 2 | 50 50 50 | 33 33 33 |
| 3 3 3 | 200 200 200 | 12 12 12 |
| 4 4 4 | 2000 2000 2000 | 38 38 38 |
对于所有数据，满足 1 ≤ a 1 < a 2 < . . . < a n ≤ 2000 , 1 ≤ T ≤ 10 , 1 ≤ v i ≤ 1 0 6 1\le a_1 < a_2 < ... < a_n \le 2000 , 1\le T \le 10 , 1 \le v_i \le 10^6 1≤a1<a2<...<an≤2000,1≤T≤10,1≤vi≤106。
题解
首先要对题意有正确的把握：由于只能知道病毒所处的状态而不是具体的活性，所以对于同一状态的所有病毒第一步所采取的状态是相同的，而这一步之后它们会被向左平移并可能被分割为一些不同状态的连续区间。于是考虑区间DP: f [ l ] [ r ] f[l][r] f[l][r]为把 [ l , r ] [l,r] [l,r]解决的最小代价和，枚举第一步即可转移，效率 O ( n 2 m ) O(n^2m) O(n2m)。
由于转移时不可避免枚举，不太可优化，考虑优化状态。注意到转移到的区间似乎都是每个状态的前缀或后缀，如果只有这些状态就是 O ( n ) O(n) O(n)的了。但可能原来的区间平移后不被分割就gg了，于是考虑强制让它经过若干次平移后被分割，那就只能枚举平移的长度，对长度做一个完全背包即可。
这篇关于DTOJ 4780. 病毒研究的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
