首页 > ACM题库 > HDU-杭电 > HDU 3140-Money Matters-动态规划-[解题报告]HOJ
2014
03-03

HDU 3140-Money Matters-动态规划-[解题报告]HOJ

Money Matters

问题描述 :

Our sad tale begins with a tight clique of friends. Together they went on a trip to the picturesque country of Molvania. During their stay, various events which are too horrible to mention occurred. The net result was that the last evening of the trip ended with a momentous exchange of "I never want to see you again!"s. A quick calculation tells you it may have been said almost 50 million times!

Back home in Scandinavia, our group of ex-friends realize that they haven’t split the costs incurred during the trip evenly. Some people may be out several thousand crowns. Settling the debts turns out to be a bit more problematic than it ought to be, as many in the group no longer wish to speak to one another, and even less to give each other money.

Naturally, you want to help out, so you ask each person to tell you how much money she owes or is owed, and whom she is still friends with. Given this information, you’re sure you can gure out if it’s possible for everyone to get even, and with money only being given between persons who are still friends.

输入:

The first line contains two integers, n (2 <= n <= 10000), and m (0 <= m <= 50000), the number of friends and the number of remaining friendships. Then n lines follow, each containing an integer o (-10000 <= o <= 10000) indicating how much each person owes (or is owed if o < 0). The sum of these values is zero. After this comes m lines giving the remaining friendships, each line containing two integers x, y (0 <= x < y <= n – 1) indicating that persons x and y are still friends.

输出:

The first line contains two integers, n (2 <= n <= 10000), and m (0 <= m <= 50000), the number of friends and the number of remaining friendships. Then n lines follow, each containing an integer o (-10000 <= o <= 10000) indicating how much each person owes (or is owed if o < 0). The sum of these values is zero. After this comes m lines giving the remaining friendships, each line containing two integers x, y (0 <= x < y <= n – 1) indicating that persons x and y are still friends.

样例输入:

5 3
100
-75
-25
-42
42
0 1
1 2
3 4
4 2
15
20
-10
-25
0 2
1 3

样例输出:

POSSIBLE
IMPOSSIBLE

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include<queue>
#include<set>
using namespace std;

int step[5] , n , m , maxsz;
int A[351] , p[5];
unsigned short f[5][923531];
unsigned short sz[5];
int st[5][8000];
bool vis[5][923531];

void init()
{
	memset(step,0,sizeof(step));
	memset(vis,0,sizeof(vis));
	memset(sz,0,sizeof(sz));
	memset(f,0,sizeof(f));
}

void getCard(int ss)
{
	memset(step,0,sizeof(step));
	int i = 4;
	int tmp = ss;
	while (ss)
	{
		if (p[i] && ss >= p[i])
		{
			step[i] = ss / p[i];
			ss -= p[i]*step[i];
		}
		--i;
	}
}

int getState()
{
	int ret = 0;
	for (int i = 4 ; i >= 1 ; --i) if (step[i])
		ret += step[i]*p[i];
	return ret;
}

void input()
{
	for (int i = 1 ; i <= n ; ++i) scanf("%d",A+i);
	for (int i = 0 ; i < m ; ++i)
	{
		int a;
		scanf("%d",&a);
		++step[a];
	}
	maxsz = 1;
	p[1] = 1;
	for (int i = 2 ; i <= 4 ; ++i)
	{
		p[i] = p[i-1];
		if (step[i-1]) p[i] *= (1+step[i-1]);
	}
	for (int i = 1 ; i <= 4 ; ++i)
		if (step[i]==0) p[i] = 0;
	for (int i = 1 ; i <= 4 ; ++i) if (step[i])
		maxsz *= step[i];
	int h = getState();
	f[1][h] = A[1];
	st[1][sz[1]++] = h;
}

void Dp(int to,int w)
{
	int j = getState();
	if (f[to][j] < w) f[to][j] = w;
	if (!vis[to][j]) 
	{
		vis[to][j] = true;
		st[to][sz[to]++] = j;
	}
}

void solve()
{
	for (int i = 1 ; i < n ; ++i)
	{
		for (int j = 0 ; j < sz[i%5] ; ++j)
		{
			int s = st[i%5][j];
			getCard(s);
			for (int k = 1 ; k <= 4 ; ++k) if (step[k])
			{
				--step[k];
				Dp((i+k)%5, f[i%5][s]+A[i+k]);
				++step[k];
			}
		}
		sz[i%5] = 0;
		memset(f[i%5],0,sizeof(f[i%5]));
		memset(vis[i%5],false,sizeof(vis[i%5]));
	}
	printf("%d\n",f[n%5][0]);
}

int main()
{
	while (scanf("%d%d",&n,&m)==2)
	{
		init();
		input();
		solve();
	}
}

参考:http://blog.csdn.net/wsx1754175/article/details/17512063


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. [email protected]

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。