SPOJ, DP

SPOJ-MINVEST.cpp

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned ull;
void setmax( int &a, int b) { if(a<b) a=b; }
ull res;
#define MAX 50005
int rem; //0..999
int YEARS; //40 

int DPN,N;
int DP[MAX];
int BN; 
int BC[11]; 
int BV[11]; 

ull fn(int n)
{
  if(n<=DPN) return DP[n];
for(int i=DPN;i<=n;i++) DP[i]=0;
	for(int i=DPN;i<=n;i++)
		for(int j=1;j<=BN;j++)
			if(i-BC[j]>=0)
				setmax( DP[i], DP[i-BC[j]]+ BV[j] );
	DPN=n;
	return DP[n];
}

int main()
{
	int tc;
	cin>>tc;
	while(tc--){
		DPN=0;
		res=0;
		rem=0;
		cin >> N >> YEARS >> BN;
		rem=N%1000;
		N=N/1000;
		for(int i=1;i<=BN;i++){
			cin >> BC[i] >> BV[i];
			BC[i]/=1000;
			}
		for(int i=1;i<=YEARS;i++)
		{
			//cout << N << '*' << res << ' ' << rem << endl;
			res=fn(N);
			N=N+(res+rem)/1000;
			rem=(res+rem)%1000;
			//cout << N << '+' << res << ' ' << rem << endl;
		}
		cout << N*1000+rem << endl; 
	}
}