[codeforces] 585D Lizard Era: Beginning || 双向dfs

原题

有n(n<=2)个任务和三个人，每次任务给出每个人能得到的值，每次任务选两个人，使n个任务结束后三个人得到的值是一样的。输出每次要派哪两个人，如果不行输出Impossible。

n<=25，3^{25肯定不行，所以考虑折半3}(n/2)。前一半我们得到a,b,c，后一半我们得到x,y,z，我们要得到a+x=b+y=c+z。将式子变形为a-b=y-x和b-c=z-y，所以用map记录a-b和b-c，以及对应的最大的a和状态（三进制表示）。然后查找y-x和z-y是否存在，得到答案即可。

#include<cstdio>

#include<map>

#include<vector>

typedef long long ll;

using namespace std;

map < pair<int,int>, pair<int,int> > mp;

map < pair<int,int>, pair<int,int> > :: iterator it;

int ans=-97797977,n,a[30][4];

ll front,back;

vector <int> v;

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') j=getchar(),fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void dfs1(int x,int l,int m,int w,int f)

{

    if (x>n/2)

    {

	it = mp.find(make_pair(l-m,w-m));

	if (it!=mp.end())

	{

	    if(l > it -> second.first)

		mp[make_pair(l-m,w-m)]=make_pair(l,f);

	}

	else mp[make_pair(l-m,w-m)]=make_pair(l,f);

	return ;

    }

    dfs1(x+1,l+a[x][1],m+a[x][2],w,f*3+0);

    dfs1(x+1,l+a[x][1],m,w+a[x][3],f*3+1);

    dfs1(x+1,l,m+a[x][2],w+a[x][3],f*3+2);

}

void dfs2(int x,int l,int m,int w,int f)

{

    if (x>n)

    {

	it=mp.find(make_pair(m-l,m-w));

	if (it!=mp.end())

	{

	    if (it->second.first+l>ans)

	    {

		ans=it->second.first+l;

		front=it->second.second;

		back=f;

	    }

	}

	return ;

    }

    dfs2(x+1,l+a[x][1],m+a[x][2],w,f*3+0);

    dfs2(x+1,l+a[x][1],m,w+a[x][3],f*3+1);

    dfs2(x+1,l,m+a[x][2],w+a[x][3],f*3+2);

}

void print(int x)

{

    if (!x) printf("LM\n");

    else if (x==1) printf("LW\n");

    else printf("MW\n");

}

int main()

{

    n=read();

    for (int i=1;i<=n;i++)

    {

	a[i][1]=read();

	a[i][2]=read();

	a[i][3]=read();

    }

    dfs1(1,0,0,0,0);

    dfs2(n/2+1,0,0,0,0);

    if (ans>-97797977)

    {

	for (int i=n-n/2;i>=1;i--)

	{

	    v.push_back(back%3);

	    back/=3;

	}

	for (int i=n/2;i>=1;i--)

	{

	    v.push_back(front%3);

	    front/=3;

	}

	for (int i=v.size()-1;i>=0;i--)

	    print(v[i]);

    }

    else printf("Impossible");

    return 0;

}

巴特西

[codeforces] 585D Lizard Era: Beginning || 双向dfs

原题

最新文章

热门文章