]]>
鎴戠殑閭 ; fanxicai2000@163.com
]]>
]]>
]]>
]]>
]]>
<font color="red">闆鐨勫ぉ絀? theorix ) 2008-12-26 20:31 鍙戣〃璇勮
]]><font color="red">闆鐨勫ぉ絀? theorix ) 2008-12-26 10:24 鍙戣〃璇勮
]]>鑳戒笉鑳芥妸榪欎釜杞崲榪囩▼鐨勬濇兂鎻忚堪涓涓嬪憿錛?
濡傝偗璧愭暀璇峰彂閭歡鍒幫細 mxx@vip.qq.com
鍏堣阿璋㈡偍浜?
]]>
<font color="red">闆鐨勫ぉ絀? theorix ) 2008-08-31 00:37 鍙戣〃璇勮
]]>鍙敤cost[i][j]琛ㄧず絎琲涓漢鍦═鏃墮棿鍐呭仛瀹宩涓猘縐嶄換鍔℃渶澶氳繕鍙仛鐨刡縐嶄換鍔℃暟
dp[i][j]琛ㄧず鍓峣涓漢鍦═鏃墮棿鍐呭仛瀹宩涓猘浠誨姟鏈澶氳繕鍙仛鐨刡縐嶄換鍔℃暟
dp[i][j]=max(dp[i-1][k]+cost[i][j-k]);
1
#include<iostream>
2using namespace std;
3int cost[109][109];
4int dp[109];
5int a[109],b[109];
6int main()
7
{
8
int ca;
9 scanf("%d",&ca);
10 while(ca--)
11
{
12 int i,j,k;
13 int n,m;
14 scanf("%d%d",&n,&m);
15 for(i=1;i<=n;i++)
16 scanf("%d%d",&a[i],&b[i]);
17 int low,high,mid;
18 low=0;
19 high=m*a[1]+m*b[1];
20 while(low<high)
21 {
22 mid=(low+high)/2;
23 for(i=1;i<=n;i++)
24 for(j=0;j<=m;j++)
25 if(mid-j*a[i]>=0)
26 cost[i][j]=(mid-j*a[i])/b[i];
27 else
28 cost[i][j]=-1;
29 for(i=0;i<=m;i++)
30 dp[i]=cost[1][i];
31 for(i=2;i<=n;i++)
32 {
33 for(j=m;j>=0;j--)
34 {
35 if(dp[j]<0)
36 continue;
37 for(k=m-j;k>=0;k--)
38 {
39 if(cost[i][k]<0)
40 continue;
41 dp[j+k]=max(dp[j+k],dp[j]+cost[i][k]);
42
}
43 }
44 if(dp[m]>=m)
45 break;
46 }
47 if(i>n)
48 low=mid+1;
49 else
50 high=mid;
51 }
52 printf("%d\n",low);
53 }
54
}
55
#include<iostream>
2
using namespace std;
3
int cost[109][109];
4
int dp[109];
5
int a[109],b[109];
6
int main()
7
{
8
int ca;
9
scanf("%d",&ca);
10
while(ca--)
11
{
12
int i,j,k;
13
int n,m;
14
scanf("%d%d",&n,&m);
15
for(i=1;i<=n;i++)
16
scanf("%d%d",&a[i],&b[i]);
17
int low,high,mid;
18
low=0;
19
high=m*a[1]+m*b[1];
20
while(low<high)
21
{
22
mid=(low+high)/2;
23
for(i=1;i<=n;i++)
24
for(j=0;j<=m;j++)
25
if(mid-j*a[i]>=0)
26
cost[i][j]=(mid-j*a[i])/b[i];
27
else
28
cost[i][j]=-1;
29
for(i=0;i<=m;i++)
30
dp[i]=cost[1][i];
31
for(i=2;i<=n;i++)
32
{
33
for(j=m;j>=0;j--)
34
{
35
if(dp[j]<0)
36
continue;
37
for(k=m-j;k>=0;k--)
38
{
39
if(cost[i][k]<0)
40
continue;
41
dp[j+k]=max(dp[j+k],dp[j]+cost[i][k]);
42
}
43
}
44
if(dp[m]>=m)
45
break;
46
}
47
if(i>n)
48
low=mid+1;
49
else
50
high=mid;
51
}
52
printf("%d\n",low);
53
}
54
}
55
]]>
]]>