首页 > 代码库 > 【动态规划】【滚动数组】【bitset】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem J. Terminal
【动态规划】【滚动数组】【bitset】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem J. Terminal
有两辆车，容量都为K，有n(10w)个人被划分成m（2k）组，依次上车，每个人上车花一秒。每一组的人都要上同一辆车，一辆车的等待时间是其停留时间*其载的人数，问最小的两辆车的总等待时间。
是f(i,j)表示前i组，j个人是否可行。w(i)表示第i组的人数。
if f(i,j)==1 then f(i+1,j+w(i+1))=1。
这是个bitset可以做的事情，每次左移以后或上f(i-1)的bitset即可。其实可以滚动数组。
然后每更新一次bitset，求一下其最左侧的1的位置，就是对于第一辆车要载的总人数，然后可以O（1）算出第二辆车的等待时间（因为第二辆车必然要接走最后一个人，由于两辆车其实等价，所以可以默认第二辆车等到最后），然后尝试更新答案。
队友代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
#include <ctime>
#include <bitset>
using namespace std;
bitset<100001> f;
struct nod{
int num;
long long last;
}t[2100];
int n,m,k,a,i,j;
long long ans;
bool cmp(nod a,nod b)
{
return a.last<b.last;
}
int main()
{
// freopen("ac.in","r",stdin);
// freopen("ac.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=n;i++)
{
scanf("%d",&a);
t[a].num++;
t[a].last=i;
}
ans=1000000000000;
sort(t+1,t+m+1,cmp);
f[0]=1;
for (i=1;i<=m;i++)
{
f=(f|(f<<t[i].num));
for (j=k;j>=0;j--)
if (f[j]==1 && n-j<=k)
{
ans=min(ans,j*t[i].last+(n-j)*t[m].last);
break;
}
}
if (ans==1000000000000) printf("-1\n"); else printf("%lld\n",ans);
}
【动态规划】【滚动数组】【bitset】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem J. Terminal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。