问一道题。。。

谢谢！

二分查找吧？

以下是来自一个蒟蒻的解答。。很(cuo)可(le)能(bie)有(da)错(wo)。
按照题意应该满足a>b>d,a>c>d，不然那种情况的直接舍掉不会得到更差的结果。
然后两个c(cpu)好像没什么用。因为2个cpu的话其他任务运行不了还不如再开一个g(gpu)。所以就变成1c,1c+1g,2c+1g。然后如果一个任务用2c+1g的话放最后或者最前面都没关系，反正没影响。
显然不可能同时两个任务用1c，因为可以一个再开一个g这样不会更慢。随意同时运行的只能是1c和1c+1g。大概假设1c总是在cpuA上运行，1c+1g总是在cpuB和gpu上运行。然后问题就简化成了等价只有两个cpu。每个cpu相对独立所以顺序从小到大就行了。
这样很好做了吧。。

首先我否定楼上的看法

首先分析题目，很明显指数级算法妥妥炸，那么看一下题目上面要求。显然，有CPU 就能运行，只有GPU 是不行的，就是说b和d都占用了所有资源

也就是把b和d取最小值，记为k，就相当于消去了一个值

消完之后吓得我想用dp了，不过我觉得是可以的

int dp[45][405][805]，dp[t][i][j]表示前t个任务占用i长的时间的可行性，用j-400表示时间差，当j-400小于0只能由a方案填上，否则由a，c皆可

#include "stdio.h"
#include "iostream"
using namespace std;
bool dp[45][405][805];
int n;
struct node{
int t1;//cpu
int t2;//cpu+gpu
int t3;//cpu*2&cpu*2+gpu
int mst;//目前最大时间上限
int sml;//目前最小时间下限
}obj[45];
inline int mn (int x, int y) { return x <y ?x :y ;}
inline int mx (int x, int y, int z) {
return (x >y ?x :y ) > z ?(x >y ?x :y ) :z;
}
inline int mn3 (int x, int y, int z) {
return (x <y ?x :y ) < z ?(x <y ?x :y ) :z;
}
void init(){
cin>>n;
int a,b,c,d,i;
for (i=1;i<=n;i++){
cin>>a>>b>>c>>d;
obj[i].t1=a;
obj[i].t2=c;
obj[i].t3=mn(b,d);
obj[i].mst=obj[i-1].mst+mx(a,c,obj[i].t3);
obj[i].sml=obj[i-1].sml+mn3(a,c,obj[i].t3);
}
}
void work(){
int i,j,k,ans;
const int tz=401,oo=100005;//向上调整
dp[0][0][tz]=true;
for (i=1;i<=n;i++){ ans=oo;
for (j=obj[i].sml;j<=obj[i].mst;j++){
for (k=tz-obj[i].mst;k<=tz+obj[i].mst;k++){
//dp[i][j][k]表示前i件物品消耗时间为j空余资源为k的方案可行性
if(k+obj[i].t1<=tz)
dp[i][j][k]|=dp[i-1][j][k+obj[i].t1];
else
dp[i][j][k]|=dp[i-1][j-k-obj[i].t1+tz][k+obj[i].t1];
//考虑第一种时间方案 1 补方案2的缺口
if(k-obj[i].t1>=tz)
dp[i][j][k]|=dp[i-1][j][k-obj[i].t1];
else
dp[i][j][k]|=dp[i-1][j-tz-obj[i].t1+k][k-obj[i].t1];
//考虑第一种时间方案 2 补方案1的缺口
if(k-obj[i].t2>=tz)
dp[i][j][k]|=dp[i-1][j][k-obj[i].t2];
else
dp[i][j][k]|=dp[i-1][j-tz-obj[i].t2+k][k-obj[i].t2];
//考虑第二种时间方案
if(j>=obj[i].t3)
dp[i][j][k]|=dp[i-1][j-obj[i].t3][k];
if(dp[i][j][k])
ans=mn(ans,j);
}
}
}
printf("%d\n",ans);
}
int main(){
freopen("cpugpu.in","r",stdin);
freopen("cpugpu.out","w",stdout);
init();
work();
return 0;
}
来不及改了，应该差不多，思想就是这样了

楼上45*405*805的内存真的不会爆？寻址不会拖吗？但是大体的算法感觉能AC

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

21回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六