网站性能需求,怎样创建微网站,如何做一个单页的网站,WordPress主题 o题目大意
有 N N N 个小时可以挤奶。其中有 m m m 个时间段可以给 Bessis 奶牛挤奶。第 i i i 个时间段为 s i s_i si ~ t i t_i ti#xff0c;可以获得 E f f i Eff_i Effi 滴奶。每次挤完奶后#xff0c;人都要休息 R R R 小时。最后问#xff0c;一共能挤出…题目大意
有 N N N 个小时可以挤奶。其中有 m m m 个时间段可以给 Bessis 奶牛挤奶。第 i i i 个时间段为 s i s_i si ~ t i t_i ti可以获得 E f f i Eff_i Effi 滴奶。每次挤完奶后人都要休息 R R R 小时。最后问一共能挤出多少滴奶。
双重选择分析
休息 R R R 小时可以归为挤奶时间段内。即第 i i i 段挤奶的时间段为 s i s_i si ~ t i t i R t_it_iR titiR。
设挤奶的最佳方案为 { a 1 , a 2 , . . . , a k } \{a_1,a_2,...,a_k\} {a1,a2,...,ak}其中 a i a_i ai 是第 i i i 个挤奶的时间段编号。同时满足 s a 2 ≥ t a 1 s_{a_2}\ge t_{a_1} sa2≥ta1 s a 3 ≥ t a 2 s_{a_3}\ge t_{a_2} sa3≥ta2以此类推。
显然为了更好的选奶牛要对奶牛按 t i t_i ti 进行排列。
对 a k a_k ak 进行双重选择分析 当 a k m a_km akm方案变为 { a 1 , a 2 , . . . , a k − 1 , m } \{a_1,a_2,...,a_{k-1},m\} {a1,a2,...,ak−1,m}方案的属性 奶量。原方案的奶量 子方案的奶量 E f f m Eff_m Effm。由于原方案求的是最大奶量所以子方案求解的也是最大奶量。可以选择的时间段范围。子方案可以选择的范围为 1 ~ m − 1 m-1 m−1。奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 s m s_m sm。 综上子方案反映的问题为从 1 ~ m − 1 m-1 m−1 个时间段中挤奶结束时间最大为 s m s_m sm 的最大奶量问题。 当 a k ≠ m a_k≠m akm方案不变。 方案的属性 奶量。原方案的奶量 子方案的奶量。可以选择的时间段范围。子方案可以选择的范围为 1 ~ m − 1 m-1 m−1。奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 N N N。 综上子方案反映的问题为从 1 ~ m − 1 m-1 m−1 个时间段中挤奶结束时间最大为 N N N 的最大奶量问题。
综上原问题的状态描述为 d p m , N dp_{m,N} dpm,N状态转移式为 d p m , N max ( d p m − 1 , s n E f f m , d p m − 1 , N ) dp_{m,N} \max(dp_{m-1,s_n}Eff_m,dp_{m-1,N}) dpm,Nmax(dpm−1,snEffm,dpm−1,N)
将其一般化可得 d p i , j max ( d p i − 1 , s i E f f i , d p i − 1 , j ) dp_{i,j}\max(dp_{i-1,s_i}Eff_i,dp_{i-1,j}) dpi,jmax(dpi−1,siEffi,dpi−1,j)需要注意的是第一种情况只有当 t i ≤ j t_i\le j ti≤j 的时候才成立。
这样做最终的时间复杂度、空间复杂度都为 O ( n m ) O(nm) O(nm)只能拿到 70 分。
示例程序
#includeiostream
#includealgorithmusing namespace std;const int N 1e3 10;struct node{int s,t,eff;bool operator (const node p)const{return t p.t;}
}cow[N];int dp[N][N * 100];int main(){int n,m,r;cin n m r;n r;for(int i 1; i m; i){cin cow[i].s cow[i].t cow[i].eff;cow[i].t cow[i].t r;}sort(cow 1,cow m 1);for(int i 0; i n; i){if(i cow[1].t) dp[1][i] cow[1].eff;else dp[1][i] 0;}for(int i 2; i m; i){for(int j 0; j n; j){if(j cow[i].t){dp[i][j] dp[i - 1][cow[i].s] cow[i].eff;}dp[i][j] max(dp[i][j],dp[i - 1][j]);}}cout dp[m][n];return 0;
}
