ZOJ 3471 压缩状态DP

时间:2024-07-23 09:03:02

这个问题要看状态怎么想,第一种直接的想法是1代表未合并,状态就从1111111 转移到 带有1个0,然后带有两个0, 但是这样子编程非常不直观。换一种思路,0代表未合并,但是我可以先合并前几个,就是说在压缩状态的过程中,状态转移的时候尽量是一个连续量的转化

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int cost[11][11];
int dp[1<<11];
int main()
{
int N;
while(cin>>N && N!=0)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
cin>>cost[i][j];
}
memset(dp, 0, sizeof(dp));
for(int tag = 0; tag < (1<<N); tag++) // tag == 0
{
for(int i = 0; i<N; i++)
{
if(tag & (1<<i)) continue;
for(int j=0; j<N; j++)
{
if(tag & (1<<j) || i==j) continue;
dp[tag ^ (1<<j)] = max(dp[tag ^ (1<<j)], dp[tag]+ cost[i][j]);
}
}
} int ret = 0;
for(int i=0; i<(1<<N); i++)
ret = max(ret, dp[i]);
cout<<ret<<endl;
}
return 0;
}