CF580D Kefa and Dishes [洛谷]


题目传送门

一、题目大意

\(kefa\)进入了一家餐厅,这家餐厅中有\(n\)个菜(\(0),\(kefa\)对第\(i\)个菜的满意度为\(a_i\)\(0<=a_i<=10^9\)),并且对于这\(n\)个菜有\(k\)个规则,如果\(kefa\)在吃完第\(x_i\)个菜之后吃了第\(y_i\)个菜(保证\(x_i、y_i\)不相等),那么会额外获得\(c_i\)\(0<=c_i<=10^9\))的满意度。\(kefa\)要吃\(m\)任意的菜(\(0),但是他希望自己吃菜的顺序得到的满意度最大,请你帮帮\(kefa\)吧!

输入第一行是三个数:\(n,m,k\)

第二行是\(n\)个数,第\(i\)个数表示\(kefa\)对第\(i\)道菜的满意度为\(a_i\)

第三行到第\(k+2\)行每行有\(3\)个数:\(x_i,y_i,c_i\),表示如果\(kefa\)在吃完第\(x_i\)道菜之后立刻吃了第\(y_i\)道菜,则会额外获得\(c_i\)的满意度

输入#1

2 2 1
1 1
2 1 1

输出#1

输入 #2

4 3 2
1 2 3 4
2 1 5
3 4 2

输出 #2

12

二、题目分析

翻译的人还好心的告诉我们要用状压。。。,其实看看数据范围也可以证明这一点,\(n<=18\)。而且"XXX"最大之流,看着就像是动态规划吧!

这题在一般状压的基础上加了一点变化:状态之间有联系,其实也是废话,状态之间没有冲突,没有关联,还用你来做题吗?

题目中说:这\(n\)个菜有\(k\)个规则,如果\(kefa\)在吃完第\(x_i\)个菜之后吃了第\(y_i\)个菜(保证\(x_i、y_i\)不相等),那么会额外获得\(c_i\) (\(0<=c_i<=10^9\))的满意度。
显然这是与吃菜的顺序有关的

但是再仔细考虑一下,会发现其实也是没有后效性

因为一道菜只与它前面的那道菜有关

显然我们可以枚举要吃的菜的前面那道菜

不妨设状态\(f[i][j]\)表示当状态为\(i\)时,最后吃的一道菜为\(j\)时获得的最大满意度

  • 当前状态\(i\) : \(f[i]\)

  • 当前状态\(i\)包含\(j\)这道菜,且前序状态不包含\(j\)

因为\(i\)需要包含了\(j\)这道菜,即\(i\)的第\(j\)位置必须是\(1\)
前序状态不能包含\(j\)这道菜,即前序状态的第\(j\)位置需要是\(0\)
也就是:\(f[i\)^\((1<

可行的状态有转移方程:
\(f[i][j]=max(f[i\)^\((1<

显然当那些状态中存在\(m\)\(1\)时(已经吃了\(m\)道菜)取\(max\)即为最后的答案

三、完整代码

#include 

using namespace std;
typedef long long LL;

const int N = 20;
int a[N], c[N][N];
int K;
int n, m;
LL f[1 << N][N], ans;

//统计某个状态中数字1的数量
int count(int x) {
    int res = 0;
    for (int i = 0; i < 32; i++) res += x >> i & 1;
    return res;
}

int main() {
    cin >> n >> m >> K;
    for (int i = 0; i < n; i++) { //下标从0开始
        cin >> a[i];
        f[1 << i][i] = a[i];      //只吃一个的初始化
    }
    while (K--) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;                 //状态压缩的套路
        c[x][y] = w;              //记录x,y的前后关联关系
    }
    for (int i = 0; i < (1 << n); i++) {        //枚举所有状态
        for (int j = 0; j < n; j++) {           //枚举每一位
            if ((i & (1 << j)) == 0) continue;  //不包含j的不是本次要计算的状态
            for (int k = 0; k < n; k++) {       //枚举前一次最后一个菜k,看看会不会获取到更大的满意度
                /*
                1、本轮吃下j,最后形成i这样的状态,那么上轮没有j,状态为 i^(1<