Coding MRain , Beta!

PKU某月的月赛中的一道题.写一写来练手.

题目大意是: 给出m个砝码(m<=16),有一个有n个节点的二叉树(n<=100),这棵树上有m个叶子节点,每个叶子节点可以挂上一颗砝码,一颗子树的重量是地下挂的所有砝码的重量之和,定义不平衡量为abs((lch.weight / root.weight)-1/2)*1000 , 要求给出一种方案,是的不平衡量的总和最小.

稍微想了下..m只有16..好吧...状态压缩的treedp.

记下f[root,state]为处理根为root的子树,底下用的砝码的状态为state..然后直接转移吧..

#include <stdio.h>
#include <memory.h>
 
typedef struct treenode{
	int lch,rch,count;
};
 
int cases,n,m,a[17],st[17][65538];
double f[102][65538],w[65538];
struct treenode tree[102];
 
int dfs(int root)             //统计每棵子树所包含的叶子节点的数目.
{
	if (tree[root].lch < 0 && tree[root].rch < 0) tree[root].count = 1;
	else tree[root].count += dfs(tree[root].lch) + dfs(tree[root].rch);
	return tree[root].count;
}
 
void calc_w()                //计算各种状态的重量
{
	memset(w,0,sizeof(w));
	for (int i=1; i<(1 << m); ++i)
		for (int j=0; j<m; ++j)
			if (i & (1 << j))
				w[i] += a[j+1];
}
 
void build_state(int state,int posi,int len)  //生成有用状态
{
	if (posi > 16) return;
	build_state(state,posi+1,len);
	state = state | (1 << (posi-1));
	st[++len][++st[len][0]] = state;
	build_state(state,posi+1,len);
}
 
double abs(double a)
{
	if (a < 0)
		a = -a;
	return a;
}
 
double search(int root,int state)           //DP主过程.(记忆化搜索)
{
	if (f[root][state] < 0)
	{
		f[root][state] = 2000000000;
		if (tree[root].count == 1)
		{
			f[root][state] = 0;
			return 0;
		}
		for (int i=1; i<=st[tree[tree[root].lch].count][0]; ++i)
		{
			int tstate = st[tree[tree[root].lch].count][i];
			if ((state & tstate) == tstate)
			{
				double temp = search(tree[root].lch,tstate)+search(tree[root].rch,state ^ tstate)+abs((w[tstate]/w[state])-0.5)*1000;
				if (f[root][state] > temp)
					f[root][state] = temp;
			}
		}
	}
	return f[root][state];
}
 
int main()
{
	scanf("%d",&cases);
	build_state(0,1,0);
	for (; cases; --cases)
	{
		scanf("%d",&n);
		memset(tree,0,sizeof(tree));
		for (int i=1; i<=n; ++i) scanf("%d %d",&tree[i].lch,&tree[i].rch);
		dfs(1);
		scanf("%d",&m);
		memset(a,0,sizeof(a));
		for (int i=1; i<=m; ++i) scanf("%d",&a[i]);
		calc_w();
		for (int i=1; i<=n; ++i)
			for (int j=1; j<(1 << m); ++j)
				f[i][j] = -1.0;
		printf("%.3lf\n",search(1,(1 << m)-1));
	}
}

DP, OI, PKU

对此我不发表任何看法.

哇哈哈哈....

Hacker, NOI, NOIP

各位同胞：

今天我站在这里，为眼前的重责大任感到谦卑，对各位的信任心怀感激，对先贤的牺牲铭记在心。我要谢谢布什总统为这个国家的服务，也感谢他在政权转移期间的宽厚和配合。

四十四位美国人发表过总统就职誓言，这些誓词或是在繁荣富强及和平宁静之际发表，或是在乌云密布，时局动荡之时。在艰困的时候，美国能箕裘相继，不仅因为居高位者有能力或愿景，也因为人民持续对先人的抱负有信心，也忠於创建我国的法统。

因此，美国才能承继下来。因此，这一代美国人也必须承继下去。

Read the rest of this entry »

奥巴马

My fellow citizens:

I stand here today humbled by the task before us, grateful for the trust you have bestowed, mindful of the sacrifices borne by our ancestors. I thank President Bush for his service to our nation, as well as the generosity and cooperation he has shown throughout this transition.

Forty-four Americans have now taken the presidential oath. The words have been spoken during rising tides of prosperity and the still waters of peace. Yet, every so often the oath is taken amidst gathering clouds and raging storms. At these moments, America has carried on not simply because of the skill or vision of those in high office, but because We the People have remained faithful to the ideals of our forbearers, and true to our founding documents.

So it has been. So it must be with this generation of Americans.

That we are in the midst of crisis is now well understood. Our nation is at war, against a far-reaching network of violence and hatred. Our economy is badly weakened, a consequence of greed and irresponsibility on the part of some, but also our collective failure to make hard choices and prepare the nation for a new age. Homes have been lost; jobs shed; businesses shuttered. Our health care is too costly; our schools fail too many; and each day brings further evidence that the ways we use energy strengthen our adversaries and threaten our planet.

These are the indicators of crisis, subject to data and statistics. Less measurable but no less profound is a sapping of confidence across our land - a nagging fear that America’s decline is inevitable, and that the next generation must lower its sights.

Read the rest of this entry »

奥巴马