织梦网站模板安装本地,俄语搜索网站,网页制作如何添加背景图片,网站建设 年终总结首先若只有一个窗口#xff0c;利用贪心#xff0c;按吃饭时间从大到小排序即可
正确性证明#xff1a;
定义 eat[i] 第i个人的吃饭时间#xff0c;time[i] 第i个人的打饭时间
延长时间T[i]max(eat[i]- ∑ji1ntimej\sum\limits_{ji1}^ntime_jji1∑ntimej ,0)
最后…首先若只有一个窗口利用贪心按吃饭时间从大到小排序即可
正确性证明
定义 eat[i] 第i个人的吃饭时间time[i] 第i个人的打饭时间
延长时间T[i]max(eat[i]- ∑ji1ntimej\sum\limits_{ji1}^ntime_jji1∑ntimej ,0)
最后的集合时间为∑j1ntimej\sum\limits_{j1}^ntime_jj1∑ntimej max{T[i] , i∈[1,N]}
将人按照eat大小从大到小排序后易证
此时max{T[i] , i∈[1,N]}最小而∑j1ntimej\sum\limits_{j1}^ntime_jj1∑ntimej为定值
所以将人按照eat大小从大到小排序后最后集合时间最短
也可以结合图理解一下 图中蓝色是打饭时间绿色是吃饭时间
易得答案是所有打饭时间之和定值加上虚线右边支出来的一截的最大长度
所以我们要尽量让支出来的长度小
因为吃饭时间长的就更容易支出去理所当然的应该尽可能往前放所以将人按吃饭时间从大到小排序
拓展到两个窗口人们排队的顺序仍然要满足吃饭慢的先打饭问题是怎么分队不难想到dp
定义 dp[i][j][k] 表示
前i个人在1号窗口打饭总时间j在2号窗口打饭总时间k最早吃完饭的时间
然后分别讨论将第i个人放在1号窗口和将第i个人放在2号窗口的情况即可
但这样明显内存会爆炸所以我们考虑优化一下空间
仔细一想发现可以去掉一维
因为 jk前i个人打饭时间总和为定值
所以 k 可以用 前i个人打饭时间总和-j 表示不需要再单独维护这一维
因此dp[i][j] 表示前i个人在1号窗口打饭总时间j最早吃完饭的时间
#includebits/stdc.h
using namespace std;
const int N210;
struct node{int a,b;
}s[N];
bool cmp(node x,node y){return x.by.b;
}
int n,sum[N],dp[N][N*N];
int main(){scanf(%d,n);for(int i1;in;i)scanf(%d%d,s[i].a,s[i].b);sort(s1,sn1,cmp);for(int i1;in;i)sum[i]sum[i-1]s[i].a;memset(dp,127,sizeof(dp));dp[0][0]0;for(int i1;in;i){for(int j0;jsum[i];j){if(js[i].a) dp[i][j]min(dp[i][j],max(dp[i-1][j-s[i].a],js[i].b));dp[i][j]min(dp[i][j],max(dp[i-1][j],sum[i]-js[i].b));}}int ans2147483647;for(int i0;isum[n];i)ansmin(ans,dp[n][i]);printf(%d\n,ans);return 0;
}参考博客
https://www.luogu.org/blog/davidblog/solution-p2577 https://phantomagony.github.io/2018/08/21/ZJOI2005-%E5%8D%88%E9%A4%90%EF%BC%88dp%EF%BC%8C%E8%B4%AA%E5%BF%83%EF%BC%89/
图片转自 https://phantomagony.github.io/2018/08/21/ZJOI2005-%E5%8D%88%E9%A4%90%EF%BC%88dp%EF%BC%8C%E8%B4%AA%E5%BF%83%EF%BC%89/
