区间dp

Posted on 2023-01-15 Edited on 2023-10-26 In ACM , 算法 Views:

Work or Rest

题意:在一个周期内任意安排假期,至少一天,使一个周期内总效率最大.每天的效率计算方法给定.

思路:对于任意一段长度为l的连续工作区间,总效率都相等,而且可以通过长度为l-1的效率得到,于是先将每个长度对应的效率预处理出来.

一看数据范围,确定是$n^2$或者$n^2logn$的算法.于是很自然的考虑区间dp.长度为l的区间可以由长度为i与l-i的区间拼出,且不会有后效性问题.由于循环不涉及顺序,那么直接顺推dp,复杂度$O(n^2)$.

For(i,1,n){
        ans[i]=rec[i-1];
        For(j,1,i-1)ans[i]=max(ans[i],ans[i-j]+rec[j-1]);
    }
    cout<<ans[n];