状态dp(位状态) boj1106 pimp my ride

Pimp My Ride
Submit: 35   Accepted:12
Time Limit: 3000MS  Memory Limit: 65536K
Description
Background
Today, there are quite a few cars, motorcycles, trucks and other vehicles out there on the streets that would seriously need some refurbishment. You have taken on this job, ripping off a few dollars from a major TV station along the way.
Of course, there's a lot of work to do, and you have decided that it's getting too much. Therefore you want to have the various jobs like painting, interior decoration and so on done by garages. Unfortunately, those garages are very specialized, so you need different garages for different jobs. More so, they tend to charge you the more the better the overall appearance of the car is. That is, a painter might charge more for a car whose interior is all leather. As those "surcharges" depend on what job is done and which jobs have been done before, you are currently trying to save money by finding an optimal order for those jobs.
Problem
Individual jobs are numbered 1 through n. Given the base price p for each job and a surcharge s (in US$) for every pair of jobs (i, j) with i != j, meaning that you have to pay additional $s for job i, if and only if job j was completed before, you are to compute the minimum total costs needed to finish all jobs.


Input
The first line contains the number of scenarios. For each scenario, an integer number of jobs n, 1 <= n <= 14, is given. Then follow n lines, each containing exactly n integers. The i-th line contains the surcharges that have to be paid in garage number i for the i-th job and the base price for job i. More precisely, on the i-th line, the i-th integer is the base price for job i and the j-th integer (j != i) is the surcharge for job i that applies if job j has been done before. The prices will be non-negative integers smaller than or equal to 100000.

Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line:
"You have officially been pimped for only $p"
with p being the minimum total price. Terminate the output for the scenario with a blank line.

Sample Input

2
2
10 10
9000 10
3
14 23 0
0 14 0
1000 9500 14


Sample Output

Scenario #1:
You have officially been pimped for only $30

Scenario #2:
You have officially been pimped for only $42

Source
TUD Programming Contest 2005, Darmstadt,

题意描述;
给定一个二维数组ARRAY[N][N]，ARRAY[i][i]表示第i个garbage需要的费用，ARRAY[i][j]（i!=j）表示如果第j个garbage在i之前选择了，那些在选择第i个garbage的时候需要额外附加的monney。
选择一个顺序，使得经过所有N个garbage所需要的费用最小。

解题思路：
状态DP。
这题二进制dp大概是这样：比如共有5个物品 编号 1 2 3 4  ，二进制 0 0 1 1 就是说已经取了3号和四号，0 0 1 1 下一个状态可以是 0 1 1 1 或1 0 1 1。DP过程就是 dp是由dp[j]再取一个编号k生成的，如果dp原先没值，就取此值，有值则取二者较小值。逐个生成最优值最后就能得1111111.....111的最优值

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

#define SIZE 14

int state[SIZE + 1][1<<SIZE], visited[SIZE + 1][1 << SIZE], monkey[210][210];
vector<int> v_used[SIZE + 1], v_bit;

void init()
{
    int i;
    for (i=0 ; i<=SIZE ; i++)
        v_used[i].clear();
    memset(state, 0, sizeof(state));
    memset(visited, 0, sizeof(visited));
}

void add_bit(int size, int pre_stat, int row)
{
    int j, i, sum, col;
    vector<int>::iterator b1, e1;

    /*将有1的位的位置入队列*/
    for (j=0 ; j<size ; j++)
    {
        if ((1 << j) & pre_stat)
            v_bit.push_back(j);
    }

    for (j=0 ; j<size ; j++)
    {
        if (!((1 << j) & pre_stat))
        {
            col = (1 << j) + pre_stat;
            e1 = v_bit.end();
            sum = 0;
            /*选择j这个点时，需要附加的额外费用*/
            for (b1 = v_bit.begin() ; b1 != e1 ; b1++)
                sum += monkey[j][*b1];
            /*加上前一个状态的最优值*/
            sum += state[row - 1][pre_stat];
            /*没有任何路径到达这个状态*/
            if (0 == visited[row][col])
            {
                state[row][col] = sum;
                visited[row][col] = 1;
                v_used[row].push_back(col);
            }
            /*已经有路径到达这个状态，取min*/
            else if (state[row][col] > sum)
            {
                state[row][col] = sum;
            }
        }
    }

    v_bit.clear();
}

int dp(int size)
{
    int i, j, pre_stat;
    vector<int>::iterator begin, end, b1, e1;

    /*初始状态*/
    state[0][0] = 0;
    v_used[0].push_back(0);

    /*从bit位上一个1到size个1*/
    for (i=1 ; i<=size ; i++)
    {
        end = v_used[i - 1].end();
        /*遍历前一个状态的所有可能值*/
        for (begin = v_used[i - 1].begin() ; begin != end ; begin++)
        {
            int t = *begin;
            /*在前一个状态的基础上求当前状态的最优值*/
            add_bit(size, t, i);
        }
    }
}

int main(int argc, char *argv[])
{
    int tcas, N, i, j, k, ret;
    cin >> tcas;
    for (i=0 ; i<tcas ; i++)
    {
        cin >> N;
        for (j=0 ; j<N ; j++)
            for (k=0 ; k<N ; k++)
                cin >> monkey[j][k];
        init();
        dp(N);

        /*最优值*/
        ret = state[N][(1 << N) - 1];
        /*加上monkey[j][j]*/
        for (j=0 ; j<N ; j++)
            ret += monkey[j][j];
        printf("Scenario #%d:\nYou have officially been pimped for only $%d\n\n", i + 1, ret);
    }
}