本文共 1047 字,大约阅读时间需要 3 分钟。
标签:完全背包
/* 题意:一定数量的本金,每年可以购买不同类型的债券(费用,利息), X年后,问能够获得的最多的本金和利息(一年之后利息又作为本金,交易无手术费)。 分析:完全背包问题。 注意:本金一直在增长,年份也不少,最后的话数组的下标会变得很大,进行内存优化, 发现费用为1000的倍数,利息可以不用管(利息还是原来的值), 只将本金和费用除以1000,利用这个来作为背包的容量,在每年之后将最大的利息加到真正的本金上面去(更新本金)。*/#include#include #include using namespace std;const int maxn = 1000005;int dp[maxn], c[15], w[15];int main(){ int N; scanf("%d", &N); while(N--) { int start, year, d; scanf("%d %d %d", &start, &year, &d); for(int i = 0; i < d;i++) { scanf("%d %d", &c[i], &w[i]); c[i] = c[i] / 1000; /// } memset(dp, 0, sizeof(dp)); // for(int i = 0; i < year; i++) //year { int temp = start / 1000; /// for(int j = 0; j < d; j++) //CompletePack template for(int k = c[j]; k <= temp; k++) dp[k] = max(dp[k], dp[k-c[j]] + w[j]); start += dp[temp]; //本金加利息 } printf("%d\n", start); } return 0;}
转载地址:http://cikxi.baihongyu.com/