题目:点击打开链接
题目大意:
有n种债券可以买,每种的价钱分别为a(a是1000的倍数),每年利息为b 。某个人共有钱tot(tot是1000的倍数),问他在y年后,最多可以有多少钱?
思路:
由于tot和a都是 1000的倍数,所有在计算时可以把他们缩小1000倍,这样节约内存和时间。
按照贪心的思想,每一年都用完全背包求出这一年最大可以得到的利息,然后下一年再用加上利息后的总钱继续计算下去……
代码:
#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<string>
#define MP make_pair
#define SQ(x) ((x)*(x))
typedef int int64;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;
const int MOD = 1000000007;
const int MAXN = 13;
const int ADD = 1000*100;
int tot, y,n;
int c[MAXN], w[MAXN];
int f[100030];
int main(){
int nCase;
scanf("%d", &nCase);
while(nCase--){
scanf("%d%d%d", &tot, &y, &n);
for(int i=0; i<n; ++i){
scanf("%d%d", &c[i], &w[i]);
c[i] /= 1000;
}
for(int i=0; i<y; ++i){
for(int j=0; j<=tot/1000; ++j)
f[j] = 0;
for(int j=0; j<n; ++j){
for(int v=c[j]; v<=tot/1000; ++v)
f[v] = max(f[v], f[v-c[j]]+w[j]);
}
tot += f[tot/1000];
}
printf("%d\n", tot);
}
return 0;
}
分享到:
相关推荐
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
2遍dp poj_3613解题报告 poj_3613解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态...
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告