「AOJ181~190」の編集履歴(バックアップ)一覧に戻る
#include<stdio.h> #include<algorithm> void setData(int m,int n){ int memo[21][102],w=0; for(int i=0;i<21;i++){ for(int j=0;j<102;j++){ memo[i][j]=2000000000; } } memo[0][0]=0; for(int i=0;i<n;i++){ scanf("%d",&w); memo[0][i+1]=memo[0][i]+w; } int t1,t2; for(int i=1;i<m;i++){ for(int j=0;j<n;j++){ for(int k=j+1;k<=n;k++){ t1=memo[i-1][j]; t1=t1==2000000000?0:t1; t2=memo[0][k]-memo[0][j]; t1=std::max(t1,t2); memo[i][k]=std::min(memo[i][k],t1); } } } printf("%d\n",memo[m-1][n]); } int main(){ int m,n; while(1){ scanf("%d %d",&m,&n); if(m==0 && n==0) break; setData(m,n); } }
#include<stdio.h> #include<map> #include<vector> int inBeakers[51]; int okBeakers[51]; int beakerSize[51]; bool butBeakers[51]; int n; bool allOK; int allCount; void saiki(int spentBeaker,int measure,int p){ if(spentBeaker==allCount && measure==0){ allOK=true; return; }else if(measure==0){ std::vector<int> memo; for(int i=0;i<n;i++){ if(inBeakers[i]>0 && butBeakers[i]==false){ inBeakers[i]--; saiki(spentBeaker,beakerSize[i],n-1); if(allOK==true) return; butBeakers[i]=true; inBeakers[i]++; memo.push_back(i); } } for(int i=0;i<memo.size();i++){ butBeakers[memo[i]]=false; } }else{ for(int i=p;i>=0;i--){ if(okBeakers[i]>0 && measure>=beakerSize[i]){ okBeakers[i]--; inBeakers[i]++; saiki(spentBeaker+1,measure-beakerSize[i],i); if(allOK==true) return; inBeakers[i]--; okBeakers[i]++; } } } } void setData(){ std::map<int,int> beakers; std::map<int,int>::iterator it; int t; allOK=false; for(int i=0;i<n;i++){ scanf("%d",&t); if(beakers.find(t)==beakers.end()){ beakers[t]=1; }else{ beakers[t]++; } } it=beakers.begin(); allCount=n=0; while(it!=beakers.end()){ okBeakers [n]=(*it).second; inBeakers [n]=0; butBeakers[n]=false; beakerSize[n]=(*it).first; allCount+=okBeakers[n]; it++; n++; } okBeakers[n-1]--; if(n>1){ saiki(1,beakerSize[n-1],n-1); }else{ allOK=true; } printf("%s\n",allOK==true?"YES":"NO"); } int main(){ while(1){ scanf("%d",&n); if(n==0) break; setData(); } }
#include<stdio.h> int main(){ int n,y,sums[7],i; while(1){ scanf("%d",&n); if(n==0) break; for(i=0;i<7;i++)sums[i]=0; for(i=0;i<n;i++){ scanf("%d",&y); y=y>60?60:y; sums[y/10]++; } for(i=0;i<7;i++){ printf("%d\n",sums[i]); } } }