首页 > ACM题库 > HDU-杭电 > HDU 4317-Unfair Nim-动态规划-[解题报告]HOJ
2015
05-23

HDU 4317-Unfair Nim-动态规划-[解题报告]HOJ

Unfair Nim

问题描述 :

Alice and Bob are tired of playing the Nim game, because they are so clever that before the beginning of the game, they have already known the result. Here is their conversation:

Bob: It’s unfair. I am always the second player, but you know, if the number of stones in each pile are distributed uniformly, at most time the first player, i.e., you, will win.
Alice: Yes, I agree with you. So I give you a chance to beat me, you are allowed to add some stones in some piles (but you can’t create a new pile) before the game starts, so that you can win as the second player.
Bob: Yeah, that’s cool. I will win definitely.
Alice: But note, you must add the minimum of the stones. If you add more stones than necessary to win, your winning will be cancelled.
Bob: er… Let me see…

For the readers who are not familiar with the Nim game (from Wikipedia):
Nim is a mathematical game of strategy in which two players take turns removing stones from distinct heaps. On each turn, a player must remove at least one stone, and may remove any number of stones provided they all come from the same heap. The player who take the last stone wins.

输入:

The first line of each test case contains an integer N (1 <= N <= 10), the number of piles at the beginning. The next line contains N positive integers, indicating the number of stones in each pile. The number of stones in each pile is no more than 1,000,000.

输出:

The first line of each test case contains an integer N (1 <= N <= 10), the number of piles at the beginning. The next line contains N positive integers, indicating the number of stones in each pile. The number of stones in each pile is no more than 1,000,000.

样例输入:

3
1 2 3
3
1 1 1
1
10

样例输出:

0
3
impossible

多校2的一道状态压缩dp,好多位运算。。。还是有点难写的

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FFF(i,a)        for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define MAX(a,b)        ((a)>(b)?(a):(b))
#define MIN(a,b)        ((a)<(b)?(a):(b))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-9;
const double pi = acos(-1.0);
const int maxn = 1<<10;
const int maxz = 23;

int n;
int dp[maxz][maxn+1];
int a[maxz];
int s[maxz];

int find(int x)
{
	int re=0;	
	while(x)
	{
		re+=(x&1);
		x>>=1;
	}
	return re;
}


void start()
{
	for(int i=0;i<maxz;i++)
	{
		for(int j=0;j<=maxn;j++)
		{
			dp[i][j]=inf;
		}
	}
	dp[0][0]=0;
	int now,temp;
	int cost;	
	int rest;
	for(int u=1;u<maxz;u++)
	{
		for(int i=0;i<(1<<n);i++)
		{
			if(dp[u-1][i]==inf)
				continue;
			now = s[u]&i;	
			temp = s[u]|i;
			for(int k=0;k<(1<<n);k++)
			{
				if(~k&now) 
					continue;
				if(~temp&k) 
					continue;
				cost = k&~now;
				cost = find(cost);
				rest = temp&~k;
				if(find(rest)%2!=0)
				{
					if(rest == (1<<n)-1)
					{
						continue;
					}
					else
					{
						cost++;
					}				
				}
				cost*=1<<(u-1);
				dp[u][k]=min(dp[u][k],cost+dp[u-1][i]);
			}
		}
	}	
	return ;
}

int main()
{
	while(cin>>n)
	{
		MM(s,0);
		for(int i=0;i<n;i++)
		{
			cin>>a[i];		
		}	
		for(int i=1;i<maxz;i++)
		{
			for(int j=0;j<n;j++)
			{
				s[i]|=((a[j]&(1<<(i-1)))&&1)<<j;
			}			
		}
		start();
		if(dp[maxz-1][0]==inf)
		{
			cout<<"impossible"<<endl;
		}
		else
		{
			cout<<dp[maxz-1][0]<<endl;
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zz_1215/article/details/7857530