1295: Fengsensei的测试

2016-12-03 12:27:45来源:CSDN作者:Z374012581人点击

题目描述

Fengsensei最近新买了一台电脑,为了对cpu有更加深入的了解,Fengsensei开始了对这台电脑的双核 cpu进行测试。为了简化问题,我们进行如下的定义,cpu有两个核分别为A和B,每次测试共有n(n<100)个任务,每个任务在A,B上执行的时间分别为Ai,Bi(Ai,Bi<100).每个任务只能在cpu的其中一个核上执行,现在Fengsensei想知道执行完这些任务所需要的最短时间是多少。

输入

第一个行为一个数k,代表样例的个数.
接下来每个样例第一行一个数n,代表任务的个数,第二行为n个非负整数,表示任务1..n在cpu A 上处理的时间Ai,第三行为n个非负整数,表示任务1..n在cpu B 上处理的时间Bi.

输出

对于每组样例,输出一个数T,表示执行完这些任务所需要的最短时间。

样例输入

1
6
2 5 7 10 5 2
3 8 4 11 3 4

样例输出

15

答案

#include<stdio.h>#include<string.h>int main(){    int k,sa[2][10000],sb[2][10000],i,j,n,a[100],b[100],s,l1,l2;    scanf("%d",&k);    while(k--)    {        scanf("%d",&n);        if(n==0) {printf("0/n");continue;}        memset(sa,0,sizeof(sa));        memset(sb,0,sizeof(sb));        for(i=0;i<n;i++)            scanf("%d",&a[i]);        for(i=0;i<n;i++)            scanf("%d",&b[i]);        sa[0][0]=1;        if(a[0]==0) sb[0][0]=0;        else {sa[0][a[0]]=1;sb[0][0]=b[0];}        for(i=1;i<n;i++)        {            l1=(i-1)%2;l2=i%2;            for(j=i*100;j>=0;j--)                if(sa[l1][j]==1)                 {                    sa[l2][j]=1;                    sb[l2][j]=sb[l1][j]+b[i];                    if(!sa[l2][j+a[i]]) {sa[l2][j+a[i]]=1;sb[l2][j+a[i]]=sb[l1][j];}                     else if(sb[l1][j]<sb[l2][j+a[i]]) sb[l2][j+a[i]]=sb[l1][j];                }            memset(sa[l1],0,i*100*sizeof(int));            memset(sb[l1],0,i*100*sizeof(int));        }        l1=(n-1)%2;        s=sb[l1][0];        for(j=0;j<10000;j++)        {            if(sa[l1][j]) {if(sb[l1][j]<j) i=j;else i=sb[l1][j];}            if(i<s) s=i;        }        printf("%d/n",s);    }    return 0;}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台