poj 1416 Shredding Company( dfs )

我的dfs真的好虚啊……,又是看的别人的博客做的 题目==

题目:http://poj.org/problem?id=1416

题意:给你两个数n,m;n表示最大数,m则是需要切割的数。

切割m,使得切割之后的数的和小于等于n。

求出最大的切割方法;

例: 50 12346

12346可以切割为 1 2 34 6和为43,这个数小于n。

12346也可以切割为1 2 3 4 6和为16,这个数也小于n;

但是43大于16,所以去43而不取16;

参考博客:http://www.cnblogs.com/luyingfeng/

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<iomanip>
#include<cmath>
#include<map>
#include<vector>
#include<algorithm>
using namespace std; int m,n,a[],t[];
int _max,r,ansk;
void dfs(int n,int sum,int now,int k,int p)
{
if(!n)
{
t[k]=now;
if(sum+now>m) return;
if(sum+now==_max) r++;
else if(sum+now>_max)
{
_max=sum+now;
r=;
ansk=k;
for(int i=; i<=k; i++)
a[i]=t[i];
}
return;
}
int mm=n%;
dfs(n/,sum,now+p*mm,k,p*);
t[k]=now;
dfs(n/,sum+now,mm,k+,);
}
int main()
{
while(cin>>m>>n&&(m!=||n!=))
{
_max=; r=;
dfs(n/,,n%,,);
if(_max==)
{
cout<<"error"<<endl;
continue;
}
if(r>)
{
cout<<"rejected"<<endl;
continue;
}
cout<<_max;
for(int i=ansk; i>=; i--)
cout<<" "<<a[i];
cout<<endl;
}
return ;
}
上一篇:ios 定位


下一篇:linux lnmp编译安装