首页 > 代码库 > zoj 3657 策略题 容易
zoj 3657 策略题 容易
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4880
因为是要去牡丹江,是浙大出题,所以找了份浙大的题,第一道水题做的就不顺啊,题看不明白,然后枚举3个数的组合,循环条件居然写错,二逼啊,这到现场肯定悲剧啊
题意:
一共有5座山,有人拿5个篮子去采蘑菇,现在他已经采了几座山上的蘑菇,之后几座山的蘑菇数量你可以自己确定。但是他要交出3个篮子,且它们的和必须是1024的倍数。否则,剩余两个篮子也要交出。之后,如果剩余数量大于1024要减去1024直到不大于。问最后剩余的最大值。
做法 分类讨论:
1、n<=3 必然1024
2、n==4 看3个篮子是从已有的4个里面出来的还是2+没采蘑菇的山
3、n==5 分能不能找到2个篮子 weight%1024==0
注意枚举3个数的组合的循环代码: 开始时,循环的开始居然写错,,,
for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) for(int k=j+1;k<n;k++) { int tmp=a[i]+a[j]+a[k]; if(tmp%1024 == 0) { flag=1; tmp=sum-tmp; while(tmp>1024)tmp-=1024; ans=max(ans,tmp); } }
AC代码
//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-8; const double pi = acos(-1.0); const int INF = 100000000; const int MAXN = 10; int n; int a[MAXN]; int sum; int ans=0; void solve4() { int flag=0; for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) for(int k=j+1;k<n;k++) { int tmp=a[i]+a[j]+a[k]; if(tmp%1024 == 0) { flag=1; tmp=sum-tmp; while(tmp>1024)tmp-=1024; ans=max(ans,tmp); } } if(flag)puts("1024"); else { for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) { int tmp=a[i]+a[j]; while(tmp>1024)tmp-=1024; ans=max(ans,tmp); } printf("%d\n",ans); } } void solve5() { int flag=0; for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) for(int k=j+1;k<n;k++) { int tmp=a[i]+a[j]+a[k]; if(tmp%1024 == 0) { flag=1; tmp=sum-tmp; while(tmp>1024)tmp-=1024; ans=max(ans,tmp); } } if(flag)printf("%d\n",ans); else puts("0"); } int main() { //IN("zoj3657.txt"); while(~scanf("%d",&n)) { sum=0; for(int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i]; ans=0; if(n<=3){puts("1024");continue;} if(n == 4)solve4(); if(n == 5)solve5(); } return 0; }
zoj 3657 策略题 容易
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。