Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这道题的结果又BUG!!敬请管理员看看!!In Reply To:这道题的结果又BUG!!敬请管理员看看!! Posted by:lcmj520 at 2010-01-30 14:46:46 > 能AC的程序; > 输入: > 18 6 > 3 > 10 6 8 > 输出: > Impossible to distribute > > 不能AC的程序; > 输入: > 18 6 > 3 > 10 6 8 > 输出: > 2 1 3 > > 但我们人为判断,不能AC的程序输出地结果才是正确的 注意,本题本人用DP,是经典的装箱问题算法。 参考代码:(不能AC的) #include <iostream> #include <vector>//记录巧克力包的编号,然后反向输出 #define MAX 1001 using namespace std; int M,L,N,sum,local,box[MAX]; short int fp[MAX],fn[MAX]; int address[MAX];//记录当前使用了哪个编号的巧克力包,等会要输入到vector中 vector<int> v; void init() { int i; sum=0; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&box[i]);sum+=box[i]; } } bool solve() { int i,j,k; memset(fp,0,sizeof(fp)); memset(fn,0,sizeof(fn)); memset(address,0,sizeof(address)); fp[0]=1; /*动态规划,装箱问题的算法*/ for(i=1;i<=N;i++) { for(j=box[i];j<=M;j++) { if(fp[j-box[i]] && !fp[j]) { fn[j]=1;address[j]=i; } } for(k=1;k<=M;k++) fp[k]=fn[k]; } for(i=M;i>0;i--) if(fp[i]) break; local=i; return (sum-local<=L); } void output() { int i,t=0; i=local; v.clear(); while(i>0) { v.push_back(address[i]); i-=box[address[i]]; t++; } printf("%d",t); vector<int>::iterator it,start=v.begin(); for(it=v.end();it>start;it--) { printf(" %d",*(it-1)); } printf("\n"); } int main(int argc, char* argv[]) { while(scanf("%d%d",&M,&L) , M&&L) { init(); if(sum<=M+L) { if(solve()) { output(); } else printf("Impossible to distribute\n"); } else printf("Impossible to distribute\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator