|
楼主 |
发表于 2023-3-13 12:57:09
|
显示全部楼层
本帖最后由 柿子饼同学 于 2023-3-13 23:01 编辑
P8087
问最小值,可以先求出能够构造出来的最小值
- pn[0] = n + 1;
- for(int i = 1; i <= n; i++){
- pn[i] = min(pn[i - 1], pos[i]);
- px[i] = max(px[i - 1], pos[i]);
- }
-
- for(int i = 1; i <= n; i++){
- if(f[i] <= n && px[f[i]] - pn[f[i]] + 1 <= i){
- cout << i;
- return 0;
- }
- }
复制代码
P2736 破锣摇滚乐队 DP, DFS
对于每个物品取舍的时候分几个情况比较好 , 这题 dfs 不用循环 , 直接 +1 就行了
DP
- F[m][t]=max{
- f[m][t] //不选当前歌曲
- f[m-1][T]+1 //用一张新的CD来存当前歌曲(m张CD不够存的情况)
- f[m][t-time[i]]+1 //一张CD放多首歌曲
- }
- //F[m][t]表示用m张CD,最后一张CD用t分钟所能存的最大歌曲数 time[i]表示第i首哥的时间
复制代码 |
|