首页 > 其他分享 >【NOIP2019普及组复赛】题3:纪念品

【NOIP2019普及组复赛】题3:纪念品

时间:2024-06-04 09:59:52浏览次数:27  
标签:10 纪念品 NOIP2019 金币 ch 小伟 100 复赛

题3:纪念品

【题目描述】

小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

1.任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;

2.卖出持有的任意一个纪念品,以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。

T 天之后,小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。

小伟现在有 M 枚金币,他想要在超能力消失后拥有尽可能多的金币。

【输入文件】

第一行包含三个正整数 T , N , M T, N, M T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T T T,纪念品数量 N N N,小伟现在拥有的金币数量 M M M。

接下来 T T T 行,每行包含 N N N 个正整数,相邻两数之间以一个空格分隔。第 i i i 行的 N N N 个正整数分别为 P i , 1 , P i , 2 , … … , P i , N P_{i,1},P_{i,2},……,P_{i,N} Pi,1​,Pi,2​,……,Pi,N​,其中 P i , j P_{i,j} Pi,j​ 表示第 i i i 天第 j j j 种纪念品的价格。

【输出文件】

输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

【输入样例1】

6 1 100
50
20
25
20
25
50

【输出样例1】

305

【样例1说明】

最佳策略是:

第二天花光所有 100 枚金币买入 5 个纪念品 1;

第三天卖出 5 个纪念品 1,获得金币 125 枚;

第四天买入 6 个纪念品 1,剩余 5 枚金币;

第六天必须卖出所有纪念品换回 300 枚金币,第四天剩余 5 枚金币,共 305 枚金币。

超能力消失后,小伟最多拥有 305 枚金币。

【输入样例2】

3 3 100
10 20 15
15 17 13
15 25 16

【输出样例2】

217

【样例2说明】

最佳策略是:

第一天花光所有金币买入 10 个纪念品 1;

第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3,剩余 1 枚金币;

第三天必须卖出所有纪念品换回 216 枚金币,第二天剩余 1 枚金币,共 217 枚金币。

超能力消失后,小伟最多拥有 217 枚金币。

【数据规模】

对于 10 % 10\% 10% 的数据, T = 1 T=1 T=1。

对于 30 % 30\% 30% 的数据, T ≤ 4 , N ≤ 4 , M ≤ 100 T≤4,N≤4,M≤100 T≤4,N≤4,M≤100,所有价格 10 ≤ P i , j ≤ 100 10≤P_{i,j}≤100 10≤Pi,j​≤100。

另有 15 % 15\% 15% 的数据, T ≤ 100 , N = 1 T≤100,N=1 T≤100,N=1。

另有 15 % 15\% 15% 的数据, T = 2 , N ≤ 100 T=2,N≤100 T=2,N≤100。

对于 100 % 100\% 100% 的数据, T ≤ 100 , N ≤ 100 , M ≤ 1 0 3 T≤100,N≤100,M≤10^3 T≤100,N≤100,M≤103,所有价格 1 ≤ P i , j ≤ 1 0 4 1≤P_{i,j}≤10^4 1≤Pi,j​≤104,数据保证任意时刻,小明手上的金币数不可能超过 1 0 4 10^4 104。

【代码如下】:

#include <bits/stdc++.h>
#define gc ch = getchar()
#define max(a, b) a > b ? a : b
using namespace std;
template <class T>
void read(T &s) {
  s = 0;
  T f = 1;
  char gc;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    gc;
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    gc;
  }
  s *= f;
}
template <class T>
void put(T s) {
  if (s < 0) putchar('-'), s = -s;
  if (s > 9) put(s / 10);
  putchar(s % 10 + '0');
}
int t, n, m, a[105][105], f[10005];
int main() {
  read(t), read(n), read(m);
  for (int i = 1; i <= t; ++i)
    for (int j = 1; j <= n; ++j) read(a[i][j]);
  for (int i = 1; i < t; ++i) {
    memset(f, 0, sizeof(f));
    for (int j = 1; j <= n; ++j)
      for (int k = a[i][j]; k <= m; ++k)
        f[k] = max(f[k], f[k - a[i][j]] + a[i + 1][j] - a[i][j]);
    m = max(f[m] + m, m);
  }
  put(m);
}

标签:10,纪念品,NOIP2019,金币,ch,小伟,100,复赛
From: https://blog.csdn.net/lpstudio/article/details/139431400

相关文章

  • 【NOIP2019普及组复赛】题1:数字游戏
    题1:数字游戏【题目描述】小K同学向小PPP同学发送了一个长度为88......
  • CSP历年复赛题-P1982 [NOIP2013 普及组] 小朋友的数字
    原题链接:https://www.luogu.com.cn/problem/P1982题意解读:特征值:第i个同学的特征值是1~i中最大子段和,分数:第i个同学分数是前1~i-1个同学的分数+特征值最大值,求最大分数。解题思路:第一步:先计算特征值f[i],f[i]等于1~i中所有数的最大子段和,所以借助最大子段和的DP方法,每次计算以i......
  • CSP历年复赛题-P1981 [NOIP2013 普及组] 表达式求值
    原题链接:https://www.luogu.com.cn/problem/P1981题意解读:中缀表达式求值,只有+,*,没有括号,保留后4位。解题思路:中缀表达式求值的典型应用,采用两个栈:符号栈、数字栈,对于没有括号的情况,只需要如下步骤:1、遍历表达式每一个字符2、如果遇到数字,则持续提取数字,保存整数到数字栈3、......
  • 【NOIP2018普及组复赛】题1:标题统计
    题1:标题统计题目描述凯凯刚写了一篇美妙的作文,请问这篇作文的标题中有多少个字符?注意:标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时,空格和换行符不计算在内。【输入格式】输入文件只有一行,一个字符串......
  • CSP历年复赛题-P1980 [NOIP2013 普及组] 计数问题
    原题链接:https://www.luogu.com.cn/record/160821231题意解读:统计1~n中x的个数。解题思路:枚举每个数,提取每一位,判断是否等于x。100分代码:#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)......
  • CSP历年复赛题-P1078 [NOIP2012 普及组] 文化之旅
    原题链接:https://www.luogu.com.cn/problem/P1078题意解读:1~n个国家,每个国家有自己的文化,不同国家文化可以相同,要从起点遍历到终点,已经学习过的文化不能重复学习,已经学习过的文化被某个文化歧视的国家也不能遍历,且不同国家之间有边,边有不同的距离,计算从起点到终点的最短路径。解......
  • CSP历年复赛题-P1075 [NOIP2012 普及组] 质因数分解
    原题链接:https://www.luogu.com.cn/problem/P1075题意解读:求n的两个素因子中较大的一个。解题思路:数论的简单题,关键在于要知道一定有一个素因子不超过sqrt(n),而另一个素因子必然大于或等于sqrt(n),这样才能减少枚举时间。100分代码:#include<bits/stdc++.h>usingnamespaces......
  • CSP历年复赛题-P1310 [NOIP2011 普及组] 表达式的值
    原题链接:https://www.luogu.com.cn/problem/P1310题意解读:+代表按位或运算,*代表按位与运算,给定一个没有填数字的表达式,要求结果为0的数字方案数。解题思路:下面一步一步,由浅入深的来解决本题思路一(20分做法):观察得知,20%的数据,只有10个符号,且没有括号,也就是对应数字最多11个,可以......
  • 【NOIP2017普及组复赛】题2:图书管理员
    题2:图书管理员【题目描述】图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。小......
  • CSP历年复赛题-P1308 [NOIP2011 普及组] 统计单词数
    原题链接:https://www.luogu.com.cn/problem/P1308题意解读:给定单词a,文本b,在b中找a的个数,并找a第一次出现的位置,注意b中任何位置可能含有多个连续空格。解题思路:通过双指针找b中每一个单词的首、尾位置i,j,与a进行一一比较即可。注意1:比较时不考虑大小写,可以统一转成小写字符tolo......