loco.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

const int N = 6004, T = 4;
int s[N]={0}, n, m, tn;    // s 1..ns
void Input( void );
int Dp( void );

int main(){
    Input();
    cout <<Dp() <<endl;
    system( "pause" );
    return 0;
}

void Input( void ){
     int a[N]={0}, i;
     cin >>n;
     for( i=1; i<=n; ++i ){
          cin >>a[i];
          a[i] += a[i-1];
     }
     cin >>m;
     if( m * 3 >= n ) tn = a[n];
     else             tn = -1;
     for( i=1; i<=m; ++i )
          s[i] = a[i];
     for( i=m+1; i<=n; ++i )
          s[i] = a[i] - a[i-m];
     return;
}

int Dp( void ){
    if( tn != -1 ) return tn;
    int f[N][T]={0}, i, j, k;
    for( i=1; i<=m; ++i )
    for( j=3; j>0; --j )
         f[i][j] = s[i];
    for( i=m+1; i<=n; ++i )
    for( j=3; j>0; --j ){
         f[i][j] = f[i-1][j];
         if( (k=f[i-m][j-1]+s[i]) > f[i][j] ) f[i][j] = k;
    }
    return f[n][3];
}