一眼看去，完全看不出来这TM是背包。知道用背包可以借之后却还是一脸蒙蔽，后来经过LZ学长的点拨，终于顿悟了！！！

 

我们设f[i] 表示用取i个（也可以没有i个）数所可以得到的最大值，那么有方程式：f[i] = max(f[i] , f[v] + d[j])    v = i - l[j];

 

wokao!!! 这TM超级秒啊！！！

直接上个核心部分看看：

for(int j = 1; j <= n; j++) { for(int i = n; i >= l[j]; i--) { int v = i - l[j]; if(f[v] == -1) continue; f[i] = max(f[i], f[v] + d[j]); ans = max(ans, f[i]); } } 整个人都震惊了。。。 接下来是证明时间，为什么这么选出来之后的解必然是存在的，而不会有重叠。。。 假设有N个数字，选了K个数字，那么所有l[s]（s属于K）的和必然小于等于N！！！ 假设其中的A点会覆盖掉B点，那么就会出现两种情况：1~ B点没有覆盖其他点，那么先把B点挑掉就可以了； 2~ B点覆盖了C点，那么就继续向下找，看看C点覆盖了那些点，一直这样往下找，直到找到一个点没有覆盖其他点为止； 那么问题来了，为啥肯定有一个点没有覆盖其他点呢？？？ 那我们就假设只有三个点（多个点其实也差不多）A,B,C，且A覆盖B，B覆盖C，C覆盖A； 那么d[A] >= A - B + 1; 那么d[b] >= B - C + 1; 那么d[C] >= C - A + 1; (字母之间相减自己加上abs) 那么d[A] + d[B] + d[C] > N; 所以肯定不存在啊！！！ 上代码！！！

#include
     
      using namespace std;int l[51], d[51], n, ans;int f[51];int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++)        scanf("%d%d", &l[i], &d[i]);    memset(f, -1, sizeof(f));    f[0] = 0;    for(int j = 1; j <= n; j++)    {        for(int i = n; i >= l[j]; i--)        {            int v = i - l[j];            if(f[v] == -1) continue;            f[i] = max(f[i], f[v] + d[j]);            ans = max(ans, f[i]);        }    }    printf("%d", ans);}