Home > Old Blog Posts > USACO 2.3.3 Zero Sum

USACO 2.3.3 Zero Sum


dfs,很弱智的dfs

代码:

/*
ID: dementr1
PROG: zerosum
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“zerosum.in”);
ofstream fout(“zerosum.out”);
int n;
void dfs(int deep, int sign[])
{
int plus[10]={},minus[10]={},pc=0,mc=0,i;
if(deep==n-1)
{
int tmp=1;
int sig=1;
int ans=0;
for(i=0;i<deep;i++)
{
if(sign[i]==0)
tmp=tmp*10+i+2;
else
{
if(sig==1) plus[pc++]=tmp;
if(sig==2) minus[mc++]=tmp;
tmp=i+2;
sig=sign[i];
}
}
if(sig==1) plus[pc++]=tmp;
if(sig==2) minus[mc++]=tmp;
for(i=0;i<pc;i++) ans+=plus[i];
for(i=0;i<mc;i++) ans-=minus[i];
if(ans==0)
{
fout<<1;
for(i=0;i<deep;i++)
{
if(sign[i]==0) fout<<” “;
else if(sign[i]==1) fout<<“+”;
else if(sign[i]==2) fout<<“-“;
fout<<i+2;
}
fout<<endl;
}
}
else
{
for(i=0;i<3;i++)
{
sign[deep]=i;
dfs(deep+1,sign);
}
}
}
int main()
{
int sign[10]={};
fin>>n;
dfs(0,sign);
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: