首页 > ACM题库 > HDU-杭电 > HDU 4049-Tourism Planning-动态规划-[解题报告]HOJ
2015
04-16

HDU 4049-Tourism Planning-动态规划-[解题报告]HOJ

Tourism Planning

问题描述 :

Several friends are planning to take tourism during the next holiday. They have selected some places to visit. They have decided which place to start their tourism and in which order to visit these places. However, anyone can leave halfway during the tourism and will never back to the tourism again if he or she is not interested in the following places. And anyone can choose not to attend the tourism if he or she is not interested in any of the places.
Each place they visited will cost every person certain amount of money. And each person has a positive value for each place, representing his or her interest in this place. To make things more complicated, if two friends visited a place together, they will get a non negative bonus because they enjoyed each other’s companion. If more than two friends visited a place together, the total bonus will be the sum of each pair of friends’ bonuses.
Your task is to decide which people should take the tourism and when each of them should leave so that the sum of the interest plus the sum of the bonuses minus the total costs is the largest. If you can’t find a plan that have a result larger than 0, just tell them to STAY HOME.

输入:

There are several cases. Each case starts with a line containing two numbers N and M ( 1<=N<=10, 1<=M<=10). N is the number of friends and M is the number of places. The next line will contain M integers Pi (1<=i<=M) , 1<=Pi<=1000, representing how much it costs for one person to visit the ith place. Then N line follows, and each line contains M integers Vij (1<=i<=N, 1<=j<=M), 1<=Vij<=1000, representing how much the ith person is interested in the jth place. Then N line follows, and each line contains N integers Bij (1<=i<=N, 1<=j<=N), 0<=Bij<=1000, Bij=0 if i=j, Bij=Bji.
A case starting with 0 0 indicates the end of input and you needn’t give an output.

输出:

There are several cases. Each case starts with a line containing two numbers N and M ( 1<=N<=10, 1<=M<=10). N is the number of friends and M is the number of places. The next line will contain M integers Pi (1<=i<=M) , 1<=Pi<=1000, representing how much it costs for one person to visit the ith place. Then N line follows, and each line contains M integers Vij (1<=i<=N, 1<=j<=M), 1<=Vij<=1000, representing how much the ith person is interested in the jth place. Then N line follows, and each line contains N integers Bij (1<=i<=N, 1<=j<=N), 0<=Bij<=1000, Bij=0 if i=j, Bij=Bji.
A case starting with 0 0 indicates the end of input and you needn’t give an output.

样例输入:

2 1
10
15
5
0 5
5 0
3 2
30 50
24 48
40 70
35 20
0 4 1
4 0 5
1 5 0
2 2
100 100
50 50
50 50
0 20
20 0
0 0

样例输出:

5
41
STAY HOME

/*******************************************************************************
    去年北京赛区网络赛水题,状态压缩DP,一开始TLE,然后发现是没初始化,应该用空间换时间来着,
接着WA,搞了半天没搞明白。。。最后发现发现一个小小的纰漏~~~
    解法就是建立状态dp[M][1 << N],用第一个状态表示第i个城市,第二个状态表示决定在这个城市
里游玩的人的状态,用二进制表示~然后就是很裸很裸的状态压缩DP了~
*******************************************************************************/
#include <iostream>
#include <functional>
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <utility>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <limits>
#include <memory>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )
#define CLR(x, k) memset((x), (k), sizeof(x))
#define CPY(t, s) memcpy((t), (s), sizeof(s))
#define SC(t, s) static_cast<t>(s)
#define LEN(s) static_cast<int>( strlen((s)) )
#define SZ(s) static_cast<int>( (s).size() )

typedef double LF;
typedef __int64 LL;		//VC
typedef unsigned __int64 ULL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VF;
typedef vector<string> VS;

template <typename T>
T sqa(const T & x)
{
	return x * x;
}
template <typename T>
T gcd(T a, T b)
{
	if (!a || !b)
	{
		return max(a, b);
	}
	T t;
	while (t = a % b)
	{
		a = b;
		b = t;
	}
	return b;
};

const int INF_INT = 0x3f3f3f3f;
const LL INF_LL = 0x7fffffffffffffffLL;		//15f
const double oo = 10e9;
const double eps = 10e-7;
const double PI = acos(-1.0);

#define  ONLINE_JUDGE

const int MAXN = 12;
const int MAXM = 12;
const int MAXS = (1 << MAXN);

int n, m, cost[MAXM], inter[MAXN][MAXM], bonus[MAXN][MAXN];
int dp[2][MAXS], maze[MAXM][MAXS];
bool hs[MAXN];
VI G[MAXS];

int valueCount(int city, int status)
{
	int res = 0, bit = 0;
	CLR(hs, false);
	for (int ind = 0; ind < n; ++ind)
	{
		if (status & (1 << ind))
		{
			hs[ind] = true;
			++bit;
		}
	}
	res -= bit * cost[city];
	for (int i = 0; i < n; ++i)
	{
		if (hs[i])
		{
			res += inter[i][city];
		}
	}
	for (int i = 0; i < n; ++i)
	{
		if (!hs[i])
		{
			continue ;
		}
		for (int j = i + 1; j < n; ++j)
		{
			if (hs[j])
			{
				res += bonus[i][j];
			}
		}
	}
	return res;
}
bool inline containsJudge(const int & lhs, const int & rhs)
{
	return (lhs & rhs) == lhs;
}
void init()
{
	int buf = (1 << n);
	for (int city = 0; city < m; ++city)
	{
		for (int ind = 0; ind < buf; ++ind)
		{
			maze[city][ind] = valueCount(city, ind);
		}
	}
	for (int i = 0; i < buf; ++i)
	{
		G[i].clear();
		for (int j = i + 1; j < buf; ++j)
		{
			if (containsJudge(i, j))
			{
				G[i].push_back(j);
			}
		}
	}
	return ;
}
int solve()
{
	CLR(dp[0], -INF_INT);
	CLR(dp[1], 0);
	int res = 0, buf = (1 << n);
	for (int ind = 0, k = 0; ind < m; ++ind, k ^= 1)
	{
		for (int crt = 0; crt < buf; ++crt)
		{
			dp[k][crt] = dp[k ^ 1][crt] + maze[ind][crt];
			res = max(res, dp[k][crt]);						//TMD相当无语了。。。
			for (VI::iterator it = G[crt].begin(); it != G[crt].end(); ++it)
			{
				int nxt = *it;
				dp[k][crt] = max(dp[k][crt], dp[k ^ 1][nxt] + maze[ind][crt]);
				res = max(res, dp[k][crt]);
			}
		}
	}
	return res;
}
void ace()
{
	int ans;
	while (cin >> n >> m, n || m)
	{
		for (int i = 0; i < m; ++i)
		{
			cin >> cost[i];
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				cin >> inter[i][j];
			}
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cin >> bonus[i][j];
			}
		}
		init();
		ans = solve();
		if (0 >= ans)
		{
			puts("STAY HOME");
			continue ;
		}
		cout << ans << endl;
	}
	return ;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ace();
	return 0;
}
/*******************************************************************************
Test Data...

2 1
10
15
5
0 5
5 0
3 2
30 50
24 48
40 70
35 20
0 4 1
4 0 5
1 5 0
2 2
100 100
50 50
50 50
0 20
20 0
0 0
*******************************************************************************/

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

参考:http://blog.csdn.net/codeforces_sphinx/article/details/7192300


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }