| ||||||||||
| 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