【XJOI】上课

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