如题:
前段时间看了点背包九讲，没能沉住气看完，后面还是要好好加工一下啊。这种背包水题还是能秒掉的。
/*
ID:sevenst4
LANG:C++
PROG:inflate
*/
#include<stdio.h>
#define MAXT 10000
#define MAXP 10000
using namespace std;int dp[MAXT+1];
int t[MAXP+1];
int f[MAXP+1];int max( int a,int b ){ return a>b?a:b; }int main()
{freopen( "inflate.in","r",stdin );freopen( "inflate.out","w",stdout );int T,P;scanf( "%d %d",&T,&P );for( int i=0;i<=T;i++ )dp[i]=0;for( int i=1;i<=P;i++ )scanf( "%d %d",&f[i],&t[i] );for( int i=1;i<=P;i++ )for( int j=t[i];j<=T;j++ )dp[j]=max( dp[j],dp[j-t[i]]+f[i] );printf( "%d\n",dp[T] );return 0;
}