800元网站建设,设计网站页面教案,建网站方法,专业个人网站建设投资的最大效益
题目背景
约翰先生获得了一大笔遗产#xff0c;他暂时还用不上这一笔钱#xff0c;他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券#xff0c;每一种债券都能在固定的投资后#xff0c;提供稳定的年利息。当然#xff0c;每一种债券的…投资的最大效益
题目背景
约翰先生获得了一大笔遗产他暂时还用不上这一笔钱他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券每一种债券都能在固定的投资后提供稳定的年利息。当然每一种债券的投资额是不同的一般来说投资越大收益也越大而且每一年还可以根据资金总额的增加更换收益更大的债券。
题目描述
例如有如下两种不同的债券
投资额 $$4000$年利息 $$400$投资额 $$3000$年利息 $$250$。
初始时有 $$10000$ 的总资产可以投资两份债券 1 债券一年获得 $$800$ 的利息而投资一份债券 1 和两份债券 2一年可获得 $$900$ 的利息两年后可获得 $$1800$ 的利息而所有的资产达到 $$11800$然后将卖掉一份债券 2换购债券 1年利息可达到 $$1050$第三年后总资产达到 $$12850$可以购买三份债券 1年利息可达到 $$1200$第四年后总资产可达到 $$14050$。
现给定若干种债券、最初的总资产帮助约翰先生计算经过 n n n 年的投资总资产的最大值。
输入格式
第一行为三个正整数 s , n , d s, n, d s,n,d分别表示最初的总资产、年数和债券的种类。
接下来 d d d 行每行表示一种债券两个正整数 a , b a, b a,b 分别表示债券的投资额和年利息。
输出格式
仅一个整数表示 n n n 年后的最大总资产。
样例 #1
样例输入 #1
10000 4 2
4000 400
3000 250样例输出 #1
14050提示
对于 100 % 100 \% 100% 的数据 1 ≤ s ≤ 10 6 1 \le s \le {10}^6 1≤s≤106 2 ≤ n ≤ 40 2 \le n \le 40 2≤n≤40 1 ≤ d ≤ 10 1 \le d \le 10 1≤d≤10 1 ≤ a ≤ 10 4 1 \le a \le {10}^4 1≤a≤104且 a a a 是 1000 1000 1000 的倍数 b b b 不超过 a a a 的 10 % 10\% 10%。
解析
对于每一年01背包然后将利息加到总金额中。
因为a都是1000的倍数所以可以优化1/1000#includebits/stdc.h
using namespace std;
#define int long long
const int N1e65;
int n,s,d,v[20],w[20],dp[N];
void solve(){scanf(%lld%lld%lld,s,n,d);for(int i1;id;i){scanf(%lld%lld,v[i],w[i]);}int sums;for(int k1;kn;k){memset(dp,0,sizeof dp);int psum/1000;for(int i1;id;i){for(int jv[i]/1000;jp;j){dp[j]max(dp[j],dp[j-v[i]/1000]w[i]);}}sumdp[p];}coutsum;
}
signed main(){int t1;
// scanf(%lld,t);while(t--) solve();return 0;
}
