dp[i+x]=max(dp[i+x] , dp[i]+a_g)1<=x<=j
因此我们对于每一个$dp[i]$我们拿他去更新$dp[i+1]$~$dp[i+j]$。
那么对应带代码上就是这样（P1725的代码）
```cpp
#include<cstdio>
#define SIZE 400000
#define MIN -999999999
using namespace std ;
int n , l , r ;
int dp[SIZE] ;
int a[SIZE] ;
inline int max ( int a , int b ) {
if ( a > b ) {
return a ;
}
return b ;
}
int main ( ) {
scanf ( "%d %d %d" , &n , &l , &r ) ;
for ( int i = 0 ; i <= n ; i ++ ) {
scanf ( "%d" , &a[i] ) ;
}
for ( int i = 0 ; i < SIZE ; i ++ ) {
dp[i] = MIN ;
}
dp[0] = 0 ;
for ( int i = 0 ; i < n ; i ++ ) { //我们是去枚举未来，所以是从0到n-1
for ( int j = 1 ; j <= r ; j ++ ) {
dp[ i + j ] = max ( dp[ i + j ] , dp[i] + a[ i + j ] ) ; //和正常DP的差别在这里
}
}
int ans = MIN ;
for ( int i = 0 ; i <= n ; i ++ ) {
ans = max ( ans , dp[i] ) ;
}
printf ( "%d\n" , ans ) ;
return 0 ;
}
```
到这里肯定有人要说了。
你这个写法根本没有优化啊，不就是换一个$O(N^2)$的朴素DP吗。
的确，写到这里本质上并没有对朴素DP又优化的作用
**但不代表后面没有啊**
## “类筛”优化
（正文开始~~之前都是水长度的~~）
我们先来看一下改写后的DP的实现形式：
我们先拿$dp[2]$更新$dp[5] ,dp[6],dp[7]
for ( int i = 0 ; i < n ; i ++ ) { //顺着枚举dp[i]
for ( int j = r ; j >= l ; j -- ) { //倒着枚举每个能够更新到的dp[i+j]
if ( dp[ i + j ] > ( dp[i] + a[ i + j ] ) ) {
break ; //如果更新失败，则直接退出
}
dp[ i + j ] = dp[i] + a[ i + j ] ;
}
}