首页 > 代码库 > HDU 3001(状态压缩dp)

HDU 3001(状态压缩dp)

状态压缩dp的第一题!

题意:Mr ACMer想要进行一次旅行,他决定访问n座城市。Mr ACMer 可以从任意城市出发,必须访问所有的城市至少一次,并且任何一个城市访问的次数不能超过2次。n座城市间有m条道路,每条道路都有一个费用。求Mr ACMer 完成旅行需要花费的最小费用。如果不能完成旅行,则输出-1。

由于城市可以最多被访问两次,所以我们用3进制数来状态压缩,每一位可以存在0,1,2这三个数。因此,如果表示状态的数在这n位上每一位都大于等于1,则就是符合题意的解,我们要从这些解中遴选出

最小花费。所以,这道题看起来是一个多起点多终点的dp,然而,我们可以把他的起点城市看成是他拜访的第1个城市,最开始这位旅行家是不在任何城市的,他抵达第1个城市的费用是0。

这样就是一个固定起点,多终点的dp了;

那么我们定义dp[i][j]---->表示到达状态(i,j)时的最小费用,其中i是我用来表示当前城市造访情况的编码数,而j表示的是我们最后造访的一个城市。

这里采用刷表法来进行状态的更新,所谓“刷表法”是指的用当前状态来更新当前状态可能影响得到的后续状态,即现在的状态值已知;

而“填表法”指的是用已经算出的所有子状态来计算现在的状态,即现在状态未知,要靠已知来计算。

刷新方程:dp[i+3v][v] = min(dp[i+3v][v],dp[i][j]+cost[v][j]);

AC时间:2270ms,有点慢。

 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define F 0x3f
#define INF 0x3f3f3f3f
#define maxn 60000
using namespace std;
int dp[maxn][11];
int cost[15][15];
int carrys[15];
int main()
{
    int n,m;
    carrys[0] = 1;
    for(int i = 1;i <= 10;++i) carrys[i] = 3 * carrys[i - 1];
    while(scanf("%d%d",&n,&m) == 2){
        memset(dp,F,sizeof(dp));
        memset(cost,F,sizeof(cost));
        int start,over,spend;
        for(int i = 0;i < m;++i){
            scanf("%d%d%d",&start,&over,&spend);
            --start,--over;
            cost[start][over] = cost[over][start] = min(cost[start][over],spend);
        }
        for(int i = 0;i < 10;++i) dp[carrys[i]][i] = 0;
        int answer = INF;
        for(int i = 1;i <= carrys[10] - 1;++i){
            bool is_qualified = true;
            for(int j = 0;j < n;++j){
                if((i / carrys[j]) % 3 == 0) is_qualified = false;
            }
            for(int j = 0;j < n;++j){
                for(int k = 0;k < n;++k){
                    if(k != j && (i / carrys[k]) % 3 < 2){
                        int u = i + carrys[k],v = k;
                        dp[u][v] = min(dp[u][v],dp[i][j] + cost[v][j]);
                    }
                }
            }
            if(is_qualified){
                for(int j = 0;j < n;++j) answer = min(answer,dp[i][j]);
            }
        }
        printf("%d\n",answer >= INF ? -1 : answer);
    }
    return 0;
}

 

HDU 3001(状态压缩dp)