1711.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1711 on 2005-09-25 at 00:09:23 */ 
#include <stdio.h>
#include <memory.h>
#define  MAXLEN  50000

int main()
{
    int c[MAXLEN], m, last, max;
    int i, j, k, l, test, d, year;
    long value[10], inter[10], money;
    
    scanf("%d", &test);
    for(i = 0; i < test; i++) {
        scanf("%ld %d", &money, &year);
        scanf("%d", &d);
        for(j = 0; j < d; j++) {
            scanf("%ld %ld", &value[j], &inter[j]);
            value[j] /= 1000;
        }
		memset(c, 0, sizeof(c));
        last = 0;
		max = 0;
        for(l = 0; l < year; l++) {
            m = money / 1000;
			for(k = last+1; k <= m; k++) {
				for(j = d-1; j >= 0; j--) {
					if(k >= value[j] && inter[j] + c[k-value[j]] > c[k]) {
						c[k] = inter[j] + c[k-value[j]];
                    }
					if(c[k] > max) {
						max = c[k];
					}
                }
            }
            last = m;
            money += max;
        }
        printf("%ld\n", money);
    }    
    
    return 0;
}