题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看Ai遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。
输入输出格式
输入格式:
共n+1行:
第1行:三个数:现在时间Ts(几点:几分),去上学的时间Te(几点:几分),爱与愁大神院子里有几棵樱花树n。
第2行~第n+1行:每行三个数:看完第i棵树的耗费时间Ti,第i棵树的美学值Ci,看第i棵树的次数Pi(Pi=0表示无数次,Pi是其他数字表示最多可看的次数Pi)。
输出格式:
只有一个整数,表示最大美学值。
输入输出样例
输入样例#1:
6:50 7:00 3 2 1 0 3 3 1 4 5 4
输出样例#1:
11
说明
100%数据:Te-Ts ≤ 1000,n ≤ 10000
样例解释:赏第一棵樱花树一次,赏第三棵樱花树2次
题解 P1833 【樱花】
放一个简单易懂的伪100分代码(需开02),不过这题爆读入优化的样子
这道题说实话并不难
这里强调一下几个地方
首先就是开始输入的那个时间了
说实话我这么输入有些笨拙,因为好像可以
scanf("%d:%d",&,&) ; 输入的样子,但本蒟蒻菜啊,不会用。
for(int i = 1 ; i <= 2 ; i ++)//输两遍
{
cin >> a >> ch >> b ;//输入
pre[t] = a * 60 + b ;//时间
t ++ ;
}
这样的话时间就用pre[2] - pre[1] 求就好了!
然后往下就是一个及其正常的混合背包:
for(int i = 1 ; i <= n ; i ++)//混合背包
if(s[i] == 0)//完全背包
{
for(int j = w[i] ; j <= m ; j ++)
f[j] = max(f[j] , f[j-w[i]] + c[i]) ;
}
else//01背包和多重背包(因为01背包s[i]为1)
for(int j = 1 ; j <= s[i] ; j ++)
for(int k = m ; k >= w[i] ; k --)
{
f[k] = max(f[k] , f[k-w[i]] + c[i]) ;
}
然后再输出便完结了!
完整代码如下:
自认为简单明了
#include<iostream>
using namespace std ;
int n , m , w[10020] , c[100010] , f[100101] ,s[10500];
int a , b ;
char ch ;
int main()
{
int pre[10];
int t=1;
for(int i = 1 ; i <= 2 ; i ++)//输两遍
{
cin >> a >> ch >> b ;//输入
pre[t] = a * 60 + b ;//时间
t ++ ;
}
m = pre[2] - pre[1] ;//求时间
cin >> n ;
for(int i = 1 ; i <= n ; i ++)
{
int p ;
cin >> w[i] >> c[i] >> s[i] ;
}
for(int i = 1 ; i <= n ; i ++)//混合背包
if(s[i] == 0)//完全背包
{
for(int j = w[i] ; j <= m ; j ++)
f[j] = max(f[j] , f[j-w[i]] + c[i]) ;
}
else//01背包和多重背包(因为01背包s[i]为1)
for(int j = 1 ; j <= s[i] ; j ++)
for(int k = m ; k >= w[i] ; k --)
{
f[k] = max(f[k] , f[k-w[i]] + c[i]) ;
}
cout << f[m] ;
}
完结散花!!