首页 > 其他分享 >洛谷 P1853 投资的最大效益 蒟蒻题解

洛谷 P1853 投资的最大效益 蒟蒻题解

时间:2024-07-10 09:46:18浏览次数:16  
标签:le 洛谷 int 题解 背包 债券 本金 P1853 include

洛谷 P1853 投资的最大效益 蒟蒻题解

题目背景

约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根据资金总额的增加,更换收益更大的债券。

题目描述

例如:有如下两种不同的债券:

  1. 投资额 $$4000$,年利息 $$400$;
  2. 投资额 $$3000$,年利息 $$250$。

初始时,有 $$10000$ 的总资产,可以投资两份债券 1 债券,一年获得 $$800$ 的利息;而投资一份债券 1 和两份债券 2,一年可获得 $$900$ 的利息,两年后,可获得 $$1800$ 的利息;而所有的资产达到 $$11800$,然后将卖掉一份债券 2,换购债券 1,年利息可达到 $$1050$;第三年后,总资产达到 $$12850$,可以购买三份债券 1,年利息可达到 $$1200$,第四年后,总资产可达到 $$14050$。

现给定若干种债券、最初的总资产,帮助约翰先生计算,经过 $n$ 年的投资,总资产的最大值。

输入格式

第一行为三个正整数 $s, n, d$,分别表示最初的总资产、年数和债券的种类。

接下来 $d$ 行,每行表示一种债券,两个正整数 $a, b$ 分别表示债券的投资额和年利息。

输出格式

仅一个整数,表示 $n$ 年后的最大总资产。

样例 #1

样例输入 #1

10000 4 2
4000 400
3000 250

样例输出 #1

14050

提示

对于 $100 %$ 的数据,$1 \le s \le {10}^6$,$2 \le n \le 40$,$1 \le d \le 10$,$1 \le a \le {10}^4$,且 $a$ 是 $1000$ 的倍数,$b$ 不超过 $a$ 的 $10%$。

解题思路:

简单的完全背包问题,但是需要动态考虑背包体积的扩大

仔细考虑dp维护什么,本此题解以利润为例

每年本金 = 债券总额 + 剩余本金 + 创收利润 同时债券总额 + 剩余本金 = 原本本金(因为债券可以无损买卖)

所以有 本金+=利润

这就是每年本金的更新

其余解释置于代码注释

代码如下:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stdio.h>
#include<vector>//Vector动态容器
#include<algorithm>
#include<stack>//栈
#include<unordered_map>//哈希表
#include<map>
#include<queue>//队列
using namespace std;
int dp[10000001];
int s, n, d;
int w[3000000];//每个债券的本金
int val[3000000];//每个债券的利润
int a;
int main(){
	cin >> s >> n >> d;//总本金 年份 种类
	for (int i = 1; i <= d; i++){//a是1000的倍数 放缩
		cin >> w[i] >> val[i];
	}
	//总本金算背包容量 债券占据背包容量的同时 会扩大背包容量(创收利润)
	//债券还可以卖出 将背包容量减轻w[i]后 背包容量对应增大w[i]
	//债券动态选择 相当于不同的元素 可以重复选取
	//动态完全背包
	//n年 每年都会在第二年创收利润
	for (int q = 1; q <= n; q++) {
		//每年本金 = 债券总额 + 剩余本金 + 创收利润 但是债券总额 + 剩余本金 = 原本本金
		//所以最终就是 s+=dp[s]
		for (int i = 1; i <= d; i++) {//计算种类
			for (int j = w[i]/1000; j <= s / 1000; j++) {//计算本金(背包体积)
				dp[j] = max(dp[j], dp[j - w[i] / 1000] + val[i]);//dp维护第二年创收利润	
			}
		}
		s = s + dp[s / 1000];
		memset(dp, 0, sizeof(dp));//每年重置
	}
	cout << s << endl;

}

包过的!!!

标签:le,洛谷,int,题解,背包,债券,本金,P1853,include
From: https://www.cnblogs.com/lgdxxs12138/p/18293222

相关文章

  • Educational_round94题解
    Educational_round94题解A.StringSimilarity(构造+思维)解题思路原字符串长度为$2*n-1$,需要匹配的字符串一共有$n$个,要使所有字符串都得到匹配,即让构造的长度为$n$的字符串每一个位置都能匹配到一个。可得到$w_i=s_{2i}$题解#include<iostream>usingnamespacestd;chars......
  • 洛谷P5594 【XR-4】模拟赛C语言
    #include<stdio.h>intmain(){ intn,m,k; inti,j; inth,l; scanf("%d%d%d",&n,&m,&k); intarr[n+1][m+1]; intday[k+1]; for(i=1;i<=n;i++){//录入数据 for(j=1;j<=m;j++){ scanf("%d&quo......
  • 洛谷P1014Cantor 表 C语言
    #include<stdio.h>intmain(){intinput;inth,k;inti,sum=0;scanf("%d",&input);for(i=1;;i++){sum+=i;//求出input数在那个范围内,i就是行数,sum就是所有行加起来数的个数if(sum>=input){h=......
  • 洛谷P1308 [NOIP2011 普及组] 统计单词数C语言
    #include<stdio.h>#include<string.h>#include<ctype.h>intmain(){charcheck[11];charstr[1000001];intf_num=0;intcount=0;inti=0;intj=0;intp=1;gets(check);gets(str);......
  • 2024年06月CCF-GESP编程能力等级认证Python编程三级真题解析
    本文收录于专栏《Python等级认证CCF-GESP真题解析》,专栏总目录:点这里,订阅后可阅读专栏内所有文章。一、单选题(每题2分,共30分)第1题小杨父母带他到某培训机构给他报名参加CCF组织的GESP认证考试的第1级,那他可以选择的认证语言有几种?()A.1B.2C.3D.4答案:C第......
  • 题解 - 修剪草坪
    题目(in洛谷)或题目(inhszxoj)题目大意给定\(n\)个非负整数\(a_1\cdotsa_n\)。现在你可以选择其中若干个数,但不能有超过\(k\)个连续的数字被选择。求选出的数字的和最大。思路简析一个比较好的思路是反向思考:选择某些间隔小于等于\(k\)(相邻间隔为\(0\))的数字,求选......
  • Codeforces Round 956 (Div. 2) 部分题解A~C
    A.ArrayDivisibility题目大意构造长度为n的数组,满足:所有j的aj之和可以被k整除,其中j是k的倍数,k的取值为1~n。思路构造序列1->n即可满足条件。代码实现voidsolve(){  lln;cin>>n;  for(inti=1;i<=n;i++)cout<<i<<"";  cout<<"\n"......
  • 洛谷 P6464 [传智杯 #2 决赛] 传送门
    通过便利每两个点之间的传送门,再便利一次其他点与传送点的路长度,没路的情况是最大值不会考虑,有路就取经过传送门和原本最短路的最小值/*台州第一深情*/include<bits/stdc++.h>usingnamespacestd;usingi64=long;usingll=longlong;typedefpair<int,int>PII;co......
  • joi2022_yo2_c 国土分割 (Land Division) 题解
    国土分割(LandDivision)推销我的洛谷博客。题意给定一个\(n\timesm\)的矩阵\(a\),你需要选择在横向或纵向分割至少一次,使得每个分割出来的小矩阵的\(a_{i,j}\)之和相等。数据范围\(1\leqslantn,m\leqslant50\)。\(1\leqslanta_{i,j}\leqslant10^5\)。思......
  • 题解 - 幻象迷宫
    题目in洛谷或题目inCF题目幻象迷宫可以认为是无限大的,不过它由若干个\(N\timesM\)的矩阵重复组成。矩阵中有的地方是道路,用\(\verb!.!\)表示;有的地方是墙,用\(\verb!#!\)表示。起始位置用\(\verb!S!\)表示。也就是对于迷宫中的一个点\((x,y)\),如果\((x\bmodn,y......