首页 > 代码库 > codeforces 189A
codeforces 189A
原题连接:
http://codeforces.com/problemset/problem/189/A
题意:
给你一个长度为n的布条,按给定的a,b,c三种长度切布条(得到的必须满足a,b,c三种之一)能得到的最多布条数;
思路:
(1)正常思考:那就是a,b,c之中先按最短的来切,然后第二短的,最后按最长的;
(2)但会有一些特殊的数据,如:53 10 11 23;(1)的想法得到的是4(即3给10,1个23),但正确答案是5(即3个11,2个10);
(3)根据(2)的特殊情况,那么就在添加一种切的方法:a,b,c之中先按第二短的来切,然后最短的,最后按最长的;最后取一下最大值即可;
ps:还有一种用动态规划的方式,怎奈本人水平过低,不会!!!!!!!!
1 #include<cstdio> 2 #include<string> 3 #include<iostream> 4 #include<algorithm> 5 6 using namespace std; 7 8 int main() 9 { 10 int n,a[3],d1=1,d2=1; 11 int la,lb,lc,i,j,k,x1,x2,x3,flag=0; 12 cin>>n>>a[0]>>a[1]>>a[2]; 13 sort(a,a+3); 14 la=n/a[0]; 15 lb=n/a[1]; 16 lc=n/a[2]; 17 for(i=la;i>=0;i--) 18 { 19 // printf("i=%d\n",i); 20 x1=n-i*a[0]; 21 // printf("!x1=%d\n",x1); 22 if(x1==0) 23 { 24 d1=i; 25 flag=1; 26 break; 27 } 28 for(j=0;j<=lb;j++) 29 { 30 // printf("j=%d\n",j); 31 x2=x1-j*a[1]; 32 // printf("@x2=%d\n",x2); 33 if(x2==0) 34 { 35 d1=i+j; 36 flag=1; 37 break; 38 } 39 if(x2<0) 40 break; 41 for(k=0;k<=lc;k++) 42 { 43 // printf("k=%d\n",k); 44 x3=x2-k*a[2]; 45 // printf("#x3=%d\n",x3); 46 if(x3==0) 47 { 48 d1=i+j+k; 49 flag=1; 50 break; 51 } 52 if(x3<0) 53 break; 54 } 55 if(flag) 56 break; 57 } 58 if(flag) 59 break; 60 } 61 flag=0; 62 for(i=lb;i>=0;i--) 63 { 64 // printf("i=%d\n",i); 65 x1=n-i*a[1]; 66 // printf("!x1=%d\n",x1); 67 if(x1==0) 68 { 69 d2=i; 70 flag=1; 71 break; 72 } 73 for(j=0;j<=la;j++) 74 { 75 // printf("j=%d\n",j); 76 x2=x1-j*a[0]; 77 // printf("@x2=%d\n",x2); 78 if(x2==0) 79 { 80 d2=i+j; 81 flag=1; 82 break; 83 } 84 if(x2<0) 85 break; 86 for(k=0;k<=lc;k++) 87 { 88 // printf("k=%d\n",k); 89 x3=x2-k*a[2]; 90 // printf("#x3=%d\n",x3); 91 if(x3==0) 92 { 93 d2=i+j+k; 94 flag=1; 95 break; 96 } 97 if(x3<0) 98 break; 99 } 100 if(flag) 101 break; 102 } 103 if(flag) 104 break; 105 } 106 // cout<<"d1="<<d1<<" d2="<<d2<<endl; 107 if(d1<d2) 108 d1=d2; 109 cout<<d1<<endl; 110 111 return 0; 112 }
欢迎大家评论!!!
codeforces 189A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。