首页 > 其他分享 >Luogu 1833 樱花

Luogu 1833 樱花

时间:2022-10-25 17:01:55浏览次数:78  
标签:樱花 1833 Pi int Luogu t4 樱花树 大神 include


题目链接:​​传送门​

题目背景

《爱与愁的故事第四弹·plant》第一章。

题目描述

爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看Ai遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。

输入格式:

共n+1行:
第1行:三个数:现在时间Ts(几点:几分),去上学的时间Te(几点:几分),爱与愁大神院子里有几棵樱花树n。
第2行~第n+1行:每行三个数:看完第i棵树的耗费时间Ti,第i棵树的美学值Ci,看第i棵树的次数Pi(Pi=0表示无数次,Pi是其他数字表示最多可看的次数Pi)。

输出格式:

只有一个整数,表示最大美学值。

输入样例

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出样例

11

每种樱花能被看的次数不同,混合背包的板子

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define

using namespace std;
int t1, t2, t3, t4, V, n, T[A], C[A], P[A], f[A];

int main() {
scanf("%d:%d", &t1, &t2);
scanf("%d:%d", &t3, &t4);
cin >> n;
V = (t3 - t1) * 60 - t2 + t4;
for (int i = 1; i <= n; i++) cin >> T[i] >> C[i] >> P[i];
for (int i = 1; i <= n; i++)
if (P[i] == 0) {
for (int j = T[i]; j <= V; j++)
f[j] = max(f[j], f[j - T[i]] + C[i]);
}
else {
for (int k = 1; k <= P[i]; k++)
for (int j = V; j >= T[i]; j--)
f[j] = max(f[j], f[j - T[i]] + C[i]);
}
cout << f[V];
}


标签:樱花,1833,Pi,int,Luogu,t4,樱花树,大神,include
From: https://blog.51cto.com/lyle/5794960

相关文章

  • Luogu 2014 选课
    题目链接:​​传送门​​题目描述在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程......
  • Luogu P4171 [JSOI2010]满汉全席
    题目链接:​​传送门​​2-sat板子题注意输入的时候可不要以为w和h后面数字只有一位*/#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#includ......
  • Luogu P4915 帕秋莉的魔导书
    题目链接:​​传送门​​动态开点是真的麻烦跟普通线段树差别还是挺大的题意就是区间前缀和的和除以区间长度#include<iostream>#include<cstdio>#include<cstring>#inc......
  • Luogu P4868 Preprefix sum
    题目链接:​​传送门​​线段树维护前缀和简单明了修改就修改当然还有更快的树状数组差分的做法*/#include<iostream>#include<cstdio>#include<cstring>#include<cs......
  • Luogu P4514 上帝造题的七分钟
    题目链接:​​传送门​​二维树状数组区间加区间求和烦人的输入#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<complex>#include<......
  • Luogu P2455 [SDOI2006]线性方程组
    题目链接:​​传送门​​高斯消元可以去下面看一下​​​https://www.bilibili.com/video/av4688674​​​听视频比瞅博客有用得多这题算比较标准的板子了各种情况都有......
  • Luogu P3833 [SHOI2012]魔法树
    题目链接:​​传送门​​树剖板子区间加,子树查询树剖里查询的时候x和y地方小于号写反T了一会a,b写成dfn[a],dfn[b]竟然还有50分又WA了一会也就交了二十遍。#include<io......
  • Luogu P1438 无聊的数列
    题目链接:​​传送门​​还是区间加等差数列时隔8个月再写一遍这个题不会的来​这里#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include......
  • Luogu P3980 [NOI2008]志愿者招募
    题目链接:​​传送门​​别人家的建图~~~~好神奇很容易想到志愿者的起始时间和终止时间连边,费用就是他的费用但是每个点还有一个人数限制必须要有那么多个人也就是那么......
  • Luogu P2221 [HAOI2012]高速公路
    题目链接:​​传送门​​维护路径期望值,带区间修改看每条路径会被统计多少次贡献非常不显然是方案数就是上面的是分子下面的是分母现在要把上面的展开看怎么维护直接......