1295: Fengsensei的测试

题目描述

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; }