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
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int L = 1100;
const int inf = 1<<30;
int dp[L][20],next[L][L],len[L],mem[L][20];
int cost[20],val[20][20],with[20][20];
int n,m,nt;
void solve()
{
int i,j,k;
nt = 1<<n;
for(i = 0; i<nt; i++)
{
len[i] = 0;
for(j = 0; j<nt; j++)//next[i][j] = k,表示由i变化的第k个状态为j
if((i&j) == j)
next[i][len[i]++] = j;
}
for(i = 0; i<nt; i++)
{
int tem = 0,cnt = 0;
for(j = 0; j<n; j++)
{
if((1<<j) & i)//J在状态之中
{
cnt++;
for(k = 0; k<j; k++)//k也在状态之中，那么为一组
if((1<<k) & i)
tem+=with[j][k];
}
}
for(j = 0; j<m; j++)//枚举城市
{
mem[i][j] = tem;
mem[i][j] -=cnt*cost[j];//减去花费
for(k = 0; k<n; k++)
{
if((1<<k) & i)//这个人存在与状态中，加上高兴值
mem[i][j]+=val[k][j];
}
}
}
for(i = 0; i<nt; i++)
{
for(j = 0; j<m; j++)
dp[i][j] = -inf;
dp[i][0] = mem[i][0];
}
for(i = 1; i<m; i++)//dp出各个状态的值
for(j = 0; j<nt; j++)
for(k = 0; k<len[j]; k++)
dp[next[j][k]][i] = max(dp[next[j][k]][i],dp[j][i-1]+mem[next[j][k]][i]);
}
int main()
{
int i,j,k;
while(~scanf("%d%d",&n,&m),n+m)
{
for(i = 0; i<m; i++)
cin>>cost[i];
for(i = 0; i<n; i++)
for(j = 0; j<m; j++)
cin>>val[i][j];
for(i = 0; i<n; i++)
for(j = 0; j<n; j++)
cin>>with[i][j];
solve();
int ans = -inf;
for(i = 0; i<nt; i++)
ans = max(ans,dp[i][m-1]);
if(ans<=0)
printf("STAY HOME\n");
else
printf("%d\n",ans);
}
return 0;
}
HDU4049：Tourism Planning(状态压缩),布布扣,bubuko.com
HDU4049：Tourism Planning(状态压缩)
原文：http://blog.csdn.net/libin56842/article/details/24550987