题面

在的CDSS的文翁路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。 一天晚上，OI组的FHH 同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来FHH 同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负，导致空气开关跳闸。 善于思考的FHH 同学考虑将路灯进行改建，以避免再次出现类似的问题。FHH同学仔细了解每盏路灯的耗电量a[i]与照明度z[i]，已知共有 N 盏电灯，并且每盏电灯都可能有不同的耗电量与照明度，现在的问题是要把这 N 盏电灯分为 M 组，新分出的每组灯的耗电量（即是该组所有打开电灯的耗电量之和）不能超过该组的电灯数目的 T 倍，在满足这样的前提下使得照明度尽可能的大，最后算出 M 组的最大照明度的和。由于每组耗电量的限制，该组中的某些电灯可能不被使用，但是仍然应该算作该组灯的数目。特别注意的是电灯按顺序给出，只能把相邻的几盏灯分在一组。 由于计算较为复杂，FHH 同学经过反复的计算仍然不能确定结果，现在就请你为他编写一个程序来解决这个问题。

输入

第一行3个整数，分别表示N、M 和 T。

接下来的N行，每行两个整数，第i+1行表示a[i]和z[i]。

输出

一个整数，表示最大照明度。

样例输入

5 2 2
1 1
2 2
3 3
4 4
5 5

样例输出

10

提示

对于70％的数据，保证有：2<=N<=80，1<=M<=35，1<=T，a[i]，z[i]<=35；

对于全部的数据，保证有：2<=N<=160，1<=M<=50，1<=T，a[i]，z[i]<=50。

解答

我们其实只要读懂题了，就不难设计出如下方案 预处理出$g[i][j]$，表示在区间$[i,j]$内选取一些电灯10KW电灯泡，四中情场专用的获得的最大亮度。至于怎么预处理，我们待会再说。 获得$g$以后，我们可以写出如下方程式 \(dp[i][j] = max(dp[i][j],dp[i-k][j-1]+g[k+1][j])\) 这样复杂度$O(N\times M)$ 那么预处理怎么做呢？

$70ptr$

暴力枚举起点和终点。复杂度$O(n^3)$,加上上面的方程，总复杂度$O(N^4M)$ 至于枚举以后，就成了一个背包，就简单了

$100ptr$

对于上面那个打表的方法，我们可以如下来做: 既然$g[i][j]$表示的是$i-j$个里面选一些电灯的最大亮度，如果我们知道了i-1盏灯的最大亮度，那么加一盏灯是不是就是体积扩大一点点，然后在原来的基础上继续更新就行了呢？不需要重复计算。在原来的基础上，每放一个，体积就增大T，那么我们直接计算出$i-n$里面选一些的最大亮度，然后通过体积查表就行了(如果i-j不选，那么在i-n内也不会选，因为向里面加灯的时候，里面的情况以及是最优了，只需要考虑加进去的灯是开着的，还是关着的) 代码：

//
// Created by dhy on 19-1-21.
//
# include <iostream>
# include <cstring>

using namespace std;
const int MAXV = 160*50+10;
const int MAXN = 169;
int g[MAXN][MAXN];
int dp[MAXN][MAXN];
int a[MAXN],z[MAXN];
int n ,m;
int T;
int temp[MAXN*50];
int main(){
    cin>>n>>m>>T;
    for(int i = 1;i<=n;i++)cin>>a[i]>>z[i];
    for(int i = 1;i<=n;i++){
        memset(temp,0, sizeof(temp));
        for(int j = i;j<=n;j++){
            for(int k = T*(n-i+1);k>=a[j];k--){//枚举体积
                temp[k] = max(temp[k],temp[k-a[j]]+z[j]);
            }
            for(int k = T*(j-i+1);k>=0;k--){//查表找最大
                g[i][j] = max(g[i][j],temp[k]);
            }
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=min(i,m);j++){
            for(int k = j-1;k<i;k++){
                dp[i][j] = max(dp[i][j],dp[k][j-1]+g[k+1][i]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}