首页 > 代码库 > JZOJ P1817：[8.27]研究性学习作业
JZOJ P1817：[8.27]研究性学习作业
传送门
老师良心推荐的二分题。7月29号第一次写，想到了裸的DP，乱搞搞过了6组，欲优化，无解，弃疗。
然后今天老师给了题解，简单看了一下。
正解是二分答案+DP验证。
二分天数$day$，然后对于每次二分出的$day$，设$f[i][j]$表示对于前$i$个人，完成$j$份A工作时可以完成的最多的$B$工作。
这个的状态转移方程很好写出：
$f[i][j]=max \left\{f[i-1][j-d/a[i].first]+(day-d)/a[i].second \right\}$
$ 0\leq d \leq day$
具体实现：
1 //OJ 1817 2 //by Cydiater 3 //2016.9.22 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define pii pair<int,int>20 const int MAXN=105;21 const int oo=0x3f3f3f3f;22 inline int read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 pii a[MAXN];29 int N,M,leftt,rightt,mid,f[MAXN][MAXN];30 namespace solution{31 inline pii get(){32 int x,y;33 x=read();y=read();34 return make_pair(x,y);35 }36 void init(){37 N=read();M=read();38 up(i,1,N)a[i]=get();39 }40 bool check(int day){41 memset(f,-10,sizeof(f));42 f[0][0]=0;43 up(i,1,N)up(j,0,M)up(d,0,day)if(j*a[i].first>=d)44 f[i][j]=max(f[i][j],f[i-1][j-d/a[i].first]+(day-d)/a[i].second);45 return f[N][M]>=M;46 }47 int slove(){48 leftt=1;rightt=100;49 while(leftt+1<rightt){50 mid=(leftt+rightt)>>1;51 if(check(mid)) rightt=mid;52 else leftt=mid;53 }54 if(check(leftt)) return leftt;55 return rightt;56 }57 }58 int main(){59 //freopen("input.in","r",stdin);60 using namespace solution;61 init();62 printf("%d\n",slove());63 return 0;64 }
JZOJ P1817：[8.27]研究性学习作业
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。