频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 2718
2013-12-09 11:33:32           
收藏   我要投稿

首先除以二,使得2边平均,然后2次dfs分别枚举a和b,更新ans。

注意0可以单独存在,但不能作为前导0.//我这里被坑了。


ps,第二次dfs也可以用next_permutation全排列



#include
#include
#include
#include
#include
using namespace std;


int a[100];
int n;
int aa,bb;
int vis[100];
int ans;
void dfs2(int now,int all,int s)
{
if(now==all)
{
bb=s;
ans=min(ans,abs(aa-bb));
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(now==0&&all==1&&a[i]==0)
{
vis[i]=1;
dfs2(now+1,all,0);
vis[i]=0;
continue;
}
if(now==0&&a[i]==0) continue;
vis[i]=1;
dfs2(now+1,all,s*10+a[i]);
vis[i]=0;
}
}
void dfs(int now,int all,int s)
{
if(now==all)
{
aa=s;
dfs2(0,n-all,0);
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(now==0&&all==1&&a[i]==0)
{
vis[i]=1;
dfs(now+1,all,0);
vis[i]=0;
continue;
}
if(now==0&&a[i]==0) continue;
vis[i]=1;
dfs(now+1,all,s*10+a[i]);
vis[i]=0;
}
}
void f(int k)
{
memset(vis,0,sizeof(vis));
dfs(0,k,0);
}
int main()
{
int cas;
char str[100];
scanf("%d",&cas);gets(str);
while(cas--)
{
n=0;
int T[11]={0};
gets(str);
for(int i=0;str[i];i++)
{
if(str[i]!=' ')
{
a[++n]=str[i]-'0';
T[a[n-1]]=1;
}
}
int top=n/2;
ans=0x3f3f3f3f;
f(top);
printf("%d\n",ans);
}
return 0;
}

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:c++流状态的查询和控制
下一篇:poj 1011
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站