XJOI】上课"/>
【XJOI】上课
题目链接
上课
题目描述
学校里有许多节课,第\(i\)节课从\(t_i\)时刻开始上,上课的时间为\(s_i\),如果上了第\(i\)节课,你的做题能力将变成\(c_i\)(是能力的数值,不是能力的增长值)。有\(N\)类作业,每类作业数量不限,每类作业完成一份所需要的时间为\(a_i\),做某类作业需要的做题能力达到\(q_i(>=q_i)\)才能完成。在每个时刻你可以选择上课、休息、做作业,如果选择上课则必须上完整节课,如果选择做作业必须花完整的\(a_i\)时间做,同一时刻只能上一节课或做一份作业。而且人的精力有限,在\(T\)时刻后必须停止学习(部分课可能上到\(T\)时刻后)。求在时限内最多可以完成几份作业。在刚开始时,你的做题能力为\(1\),时刻为\(1\)。
输入格式:
第一行三个整数\(T\),\(M\),\(N\),表示总时间,有\(M\)节课,有\(N\)类作业。
接下来\(M\)行每行三个整数\(t_i\),\(s_i\),\(c_i\)。
接下来\(N\)行每行两个整数\(a_i\),\(q_i\)。
输出格式:
共一行,一个整数\(ans\),表示时限内最多可以完成几份作业。
样例输入:
10 1 2 3 2 5 4 1 1 3
样例输出:
6
数据范围:
\(20%\)的数据满足\(M,N<=4\),\(T<=15\)。
\(50%\)的数据满足\(M<=100\),\(N<=1000\),\(T<=1000\)。
\(100%\)的数据满足\(M<=1000\),\(N<=100000\),\(T<=100000\),\(1<=c_i<=100\),\(1<=a_i\)、\(t_i<=T\),\(1<=q_i<=100\)。
时间限制:
1S
空间限制:
64M
提示:
remove!!!
题解
有\(N\)节课,每节课能使你的做题能力(智商)变成一个值。
给你\(M\)种作业,需要一定的时间和一定的做题能力。(刚开始以为每种题目只能做一次,想了半天o(╥﹏╥)o)
因为每一种作业花费“时间”时增加的价值固定为1.
这样我们就能预处理出每种能力做1份作业最少需要多少时间。
memset(mn,0x3f,sizeof(mn));
for(int j=1;j<=n;j++){scanf("%d%d",&x,&y);mn[y]=min(mn[y],x);
}
for(int j=1;j<=102;j++)mn[j]=min(mn[j],mn[j-1]);
我们看到\(M\)的范围只有\(1000\)那么我们就可以dp一下了。
\(dp[j]\)表示到第\(j\)节课之前做多可以做多少作业。
这样枚举\(j\)之前的每节课上完后一直做作业到第\(j\)节课之前能做多少作业就行了。
转移方程为:\(dp[j]=max(dp[j],dp[i]+\frac{a[j].t-a[i].t-a[i].s}{mn[a[i].c]}\)
上代码:
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
int t,n,m;
int x,y;
struct aa{int t,s,c;
}a[1009];
int mn[119];
int dp[1009];
bool cmp(aa x,aa y){return x.t<y.t;
}
int main(){memset(mn,0x3f,sizeof(mn));scanf("%d%d%d",&t,&m,&n);for(int j=1;j<=m;j++)scanf("%d%d%d",&a[j].t,&a[j].s,&a[j].c);m++;a[m].t=t+1;sort(a+1,a+m+1,cmp);a[0].t=a[0].c=1;for(int j=1;j<=n;j++){scanf("%d%d",&x,&y);mn[y]=min(mn[y],x);}for(int j=1;j<=102;j++)mn[j]=min(mn[j],mn[j-1]);for(int j=1;j<=m;j++){for(int i=0;i<j;i++){if(a[i].t+a[i].s-1>=a[j].t) continue;dp[j]=max(dp[j],dp[i]+(a[j].t-a[i].t-a[i].s)/mn[a[i].c]);}}printf("%d\n",dp[m]);return 0;
}
转载于:.html
更多推荐
【XJOI】上课
发布评论