psolve1 ac.cpp

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

// f[i][j] 完成前 j 个问题所用最少月数，其中前 i 个在倒数第二个月之前完成 
#include <fstream>
using namespace std;

ifstream  fin( "psolve.in" );
ofstream fout( "psolve.out" );

const int PP = 303, OO = 212345678;
int p, m, f[PP][PP], sa[PP], sb[PP];

int main(){
    int i, j, k;
    fin >>m >>p;
    sa[0] = sb[0] = 0;
    for( k=1; k<=p; ++k ){
         fin >>i >>j;
         sa[k] = sa[k-1] + i;
         sb[k] = sb[k-1] + j;
    }
    
    for( i=0; i<=p; ++i )
    for( j=0; j<=p; ++j )
         f[i][j] = OO;
    f[0][0] = 2;
    for( j=1; j<=p; ++j )
    for( i=0; i<=j; ++i )
    for( k=0; k<=i; ++k ){
         if( (f[i][j]>f[k][i]+1) && (sb[j]-sb[i]<=m) && (sb[i]-sb[k]+sa[j]-sa[i]<=m) ){
             f[i][j] = f[k][i] + 1;
         }
    }
    
    k = OO;
    for( i=0; i<=p; ++i )
         if( k > f[i][p] ) k = f[i][p];
    fout <<k <<endl;
    return 0;
}