2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)C Chino with Queue(状压dp)

C.Chino with Queue

题目描述
Chino的数学很差，因此Cocoa非常担心。今天，Cocoa准备教Chino和排队有关的问题。
我们总是会学各种排列组合的问题，那些题目大多数都是套路。而Cocoa不喜欢套路。
通常来说，每个人在排队的时候都会对前一个人有所意见，而如果他们排在第一个，也会颇有微词。因此，排一个尽可能让更多人满意的队伍是一件难事。
假设我们要给n个人排队，Wij表示了j排在i之前一个给i带来的舒适度，Wii而就表示了i排在第一位的舒适度。
通过一番模拟，Chino当然计算出了最优的方案，不过Cocoa希望Chino能计算地快一点。
题目对于Chino来说太难啦，你能帮一帮Chino吗？
输入描述:
第一行是一个正整数n；接下来是一个n x n的矩阵Wi,j
输出描述:
输出所有人舒适度之和的最大值
示例1
输入
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
输出
13
一看数据范围再看看题意大概就知道是一个状态dp的题目，写的时候不知道怎么写状态，比赛结束之后看了别人的代码才恍然大悟，如果写得不对欢迎各位大佬指出来

题解

dp[i][j]表示状态为i的时候最后一位是j的最大价值。
这个状态是由某一个状态推出来的，这个不太好想，那么我们想我们这个状态可以推出那些状态呢。思考一下我们发现，dp[i][j]可以推出dp[i|(1<<k)][k]，其中k必须保证没有在i这个状态中出现过。好了，那我们这个题目就做完了
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+w[k][j]);

/**
 *　　　　　　　　┏┓　　 　┏┓
 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃　　　━　　 　┃
 * 　　　　　　　┃　＞　　　＜　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃...　⌒　... 　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting
 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┗━━━┓
 * 　　　　　　　　　┃　　　　　　　┣┓
 * 　　　　　　　　　┃　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛
 */
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define  inf  0x3f3f3f3f
#define ll long long
#define mod 1000000007
const ll maxn=(1<<19)+5;
int w[20][20],num[20];
ll dp[maxn][25];
ll n,ans;
inline int in() {//输入挂
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void out(ll a){//输出外挂
    if (a < 0){
       putchar('-');
        a = -a;
    }
    if (a >= 10){
       out(a / 10);
    }
    putchar(a % 10 + '0');
}

int main(){
    n=in();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            w[i][j]=in();
        }
    }
    //dp[i][j]表示当前状态为i，最后放的一个人是j的最大价值
    for(int i=0;i<n;i++)dp[1<<i][i]=w[i][i];
    for(int sta=0;sta<(1<<n);sta++){//枚举状态一共有1<<n种状态
        for(int j=0;j<n;j++){//枚举前一个人是j
            if((sta&(1<<j))==0)continue;//如果这个状态上没有j，continue;
            for(int k=0;k<n;k++){//枚举后一个人是k
                if(sta&(1<<k))continue;//如果k已经出现过，continue;
                //如果没出现过，那么dp一下
                dp[sta|(1<<k)][k]=max(dp[sta|(1<<k)][k],dp[sta][j]+w[k][j]);
                ans=max(ans,dp[sta|(1<<k)][k]);
            }
        }
    }
    out(ans);
}
/*
 4
 1 2 3 4
 1 2 3 4
 1 2 3 4
 1 2 3 4
 */

代码看的是@MNNU_嘤嘤嘤
感谢。