首页 > 代码库 > usaco-5.3-milk4-passed
usaco-5.3-milk4-passed
这个要用动态规划，呵呵:
这道题要用到迭代加深搜索(DFSID)。由于要求输出的是使用最少的牛奶桶，所以要先找牛奶桶数量为1的时候所有的组合，如果没有解再找牛奶桶数量为2...直到牛奶桶数量为P。
当搜索到一个组合，判断用这些牛奶桶是否能组成目标解的时候，可以用动态规划的方法来做。设f[i]是当需求的牛奶为i时，能否形成这个组合，是一个布尔型数组。 初始条件 f[0]=true 状态转移方程 f[i]=f[i] or f[ i-v[j] ] (j为使用的所有牛奶桶) 目标状态 f[Q] 如果f[Q]为true，则当前解合法，直接输出即可。
但是如果仅仅这样写还是有一组数据过不去，需要进行一些优化。要优化动态规划的过程。 注意一个重要的信息，找到的组合中，每个牛奶桶至少用了一次。上面的状态转移方程中有许多某个牛奶桶使用0次的冗余状态。可以在初始的时候对(i=1..Q/v[第一个桶]) f[ i*v[第一个桶] ]赋值为true。对每个其他的桶的状态可以直接由前面的状态得出。
/*ID: qq104801LANG: C++TASK: milk4QQ:104804687*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>#include <cmath>using namespace std;#define loop(i,n) for(int i=0;i<(n);i++)#define loop2(i,n) for(int i=1;i<=(n);i++)const int maxp=101;const int maxq=20001;const int inf=1<<30;int q,p,ans,v[maxp],use[maxp];int cmp(const void *a,const void *b){ return *(int*)a<*(int*)b?-1:1;}void print(){ cout<<ans; loop2(i,ans) cout<<‘ ‘<<v[use[i]]; cout<<endl; exit(0); //here exit,halt}void judge(){ int i,j; bool f[maxq]; memset(f,0,sizeof(f)); for(i=1;i<=q/v[use[1]];i++) f[i*v[use[1]]]=true; for(i=2;i<=ans;i++) for(j=v[use[i]];j<=q;j++) f[j] |=f[j-v[use[i]]]; if(f[q]) print();}void dfs(int k){ int i,j; for(i=use[k-1]+1;i<=p-ans+k;i++) { use[k]=i; if(k==ans) judge(); else dfs(k+1); }}void test(){ freopen("milk4.in","r",stdin); freopen("milk4.out","w",stdout); cin>>q>>p; loop2(i,p) cin>>v[i]; qsort(v+1,p,sizeof(v[0]),cmp); for(ans=1;ans<=p;ans++) dfs(1);}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 31 users onlineCHN/9 GEO/10 IRN/1 MYS/1 TUR/1 USA/9USER: cn tom [qq104801]TASK: milk4LANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.003 secs, 3376 KB] Test 2: TEST OK [0.008 secs, 3376 KB] Test 3: TEST OK [0.005 secs, 3376 KB] Test 4: TEST OK [0.008 secs, 3376 KB] Test 5: TEST OK [0.005 secs, 3376 KB] Test 6: TEST OK [0.008 secs, 3376 KB] Test 7: TEST OK [0.078 secs, 3376 KB] Test 8: TEST OK [0.016 secs, 3376 KB] Test 9: TEST OK [0.008 secs, 3376 KB] Test 10: TEST OK [0.076 secs, 3376 KB]All tests OK.YOUR PROGRAM (‘milk4‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 [length 11 bytes] ----163357------- test 2 [length 11 bytes] ----203124------- test 3 [length 13 bytes] ----59371113------- test 4 [length 13 bytes] ----872228997------- test 5 [length 25 bytes] ----323597101103107119------- test 6 [length 20 bytes] ----200003233151413------- test 7 [length 509 bytes] ----53341001009101310191021103110331039104910511061106310691087109110931097110311091117112311291151115311631171118111871193120112131217122312291231123712491259127712791283128912911297130113031307131913211327136113671373138113991409142314271429143314391447145114531459147114811483148714891493149915111523153115431549155315591567157115791583159716011607160916131619162116271637165716631667166916931697169917091721------- test 8 [length 508 bytes] ----1538310099799810001003100710121018102510331042105210631075108811021117113311501168118712071228125012731297132213481375140314321462149315251558159216271663170017381777181718581900194319872032207821252173222222722323237524282482253725932650270827672827288829503013307731423208327533433412348235533625369837723847392340004078415742374318440044834567465247384825491350025092518352755368546255575653575058485947------- test 9 [length 104 bytes] ----1982920708727764825916104312121429170020312428289734444075479656136532755987009961------- test 10 [length 471 bytes] ----167379490490991692593694996498110001021104410691096112511561189122412611300134113841429147615251576162916841741180018611924198920562125219622692344242125002581266427492836292530163109320433013400350136043709381639254036414942644381450046214744486949965125525653895524566158005941608462296376652566766829698471417300746176247789795681258296846986448821900091819364954997369925
usaco-5.3-milk4-passed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。