Tourism Planning

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1051    Accepted Submission(s): 460

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

题目大意：

输入描述：

第一行两个数字表示，有n个人，m个城市

接下来 m个数字表示每个人参观这些城市的花费

接下来n行m列表示每个人参观每个城市得到的满意度

接下来n行n列表示每参观一个城市互相之间的影响的额外满意度，Bij (1<=i<=N, 1<=j<=N), 0<=Bij<=1000, Bij=0 if i=j, Bij=Bji.

你可以安排这n个人中的任意多个依次参观这m个城市0~m-1，中途也可以让一个人退出，退出后不能再回来，问你最大的值？

值 = 每个人参观每个城市得到的满意度的和 + 互相之间的影响增加的满意度和 - 参观花费和 。

解题思路：

这题的核心是DP

（1）因为n<=10 ，m<=10 ，数据比较小，可以考虑比较暴力的做法，DP就是一个很好的暴力。

（2）很容易就想到这样的DP方程 DP[sum][k]=max{ DP[son][k+1] } + value[sum][k];

sum 就是用2进制表示的有哪些人，son就是sum的子状态，表示sum中一些人半途离开了还剩下的人,

k表示当前是在访问到哪个城市了,DP[sum][k]记录的是在这个状态下要求的最大值。

当有sum这些人访问到k这个城市时候，这时候中途退了一些人，转移到了son这些人，k+1城市 这个状态 

转移的花费就是 sum这些人在k这个城市获得的总值，记为 value[sum][k]。

（3）唯一有点麻烦的就是value[sum][k]的数据预处理，这个暴力枚举。

解题代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn=11;
int n,m;//n people,m cities
int cost[maxn],a[maxn][maxn],b[maxn][maxn];
int dp[(1<<maxn)][maxn],vis[(1<<maxn)][maxn],val[(1<<maxn)][maxn],marked;

void input(){
	marked++;
	for(int i=0;i<m;i++) scanf("%d",&cost[i]);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<m;i++){
		for(int sum=0;sum<(1<<n);sum++){
			val[sum][i]=0;
			for(int p1=0;p1<n;p1++){
				if( !((1<<p1)&sum) ) continue;
				for(int p2=0;p2<p1;p2++){
					if( (1<<p2)&sum ){
						val[sum][i]+=b[p1][p2];
					}
				}
				val[sum][i]+=a[p1][i]-cost[i];
			}
		}
	}
}

int DP(int sum,int k){
	if(k>=m) return 0;
	if(vis[sum][k]==marked) return dp[sum][k];
	int ans=0;
	for(int x=sum;x!=0;x=(x-1)&sum ){//for every son state
		int tmp=DP(x,k+1)+val[sum][k];
		if(tmp>ans) ans=tmp;
	}
	vis[sum][k]=marked;
	return dp[sum][k]=ans;
}

void solve(){
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		if(DP(i,0)>ans) ans=DP(i,0);
	}
	if(ans==0) printf("STAY HOME\n");
	else printf("%d\n",ans);
}


int main(){
	while(scanf("%d%d",&n,&m)!=EOF && (n||m) ){
		input();
		solve();
	}
	return 0;
}

HDU 4049 Tourism Planning（动态规划）