Codeforces,Kefa and Dishes,状态压缩DP_kefa and pack伪代码

题意：

给定n个物品，每个物品都有一个满意度v，现在从n个物品中选取m个，选的过程中有几个规则，它们是基于选择顺序给出的规则，例如：选择的过程中a和b相邻，且a在b的前面，则满意度增加c，现在给出了k个这样的规则。问你根据这些规则，从n个物品中选取m个的最大满意度是多少。

范围：

0<=n,m<=18，k<=n*(n-1)，v<=10^9

分析：

通过n和m的范围，很容易想到对状态进行压缩。

我的初始错误解法：dp[mask]表示当前的状态，然后遍历n个物品，若i不再mask中，则加入；并且遍历与i有关的规则，若i,j都不在，在加入i,j。

上述状态表示不知道当前结尾的物品是什么，反应的信息不够，最终任何两个相邻的物品，都要根据规则来进行加分，但是上述状态是没法做到这样的。

所以改变状态表示dp[mask][i]表示当前物品状态为mask，且结尾的物品为i，这样就可以根据物品i和规则来进行转移了。

注意：因为满意度可以为0，所以初始化dp[][]的时候，要初始化为-1，初始化为0是错的。

具体代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
#define N 300010
typedef long long LL;
#define aa frist
#define bb second
int n,m,k;
LL a[20],dp[N][19];
//vector<pair<int,LL> > rule[20];
int cal(int v)
{
    int num=0;
    while(v>0)
    {
        if(v&1) num++;
        v/=2;
    }
    return num;
}
LL rs[20][20];
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF) //
    {
        for(int i=0; i<n; i++)
        {
            scanf("%I64d",&a[i]);
//            rule[i].clear();
        }
        memset(rs,0,sizeof(rs));
        for(int i=0; i<k; i++)
        {
            int x,y;
            LL c;
            scanf("%d%d%I64d",&x,&y,&c);
            x--;
            y--;
//            rule[x].push_back(make_pair(y,c));
            rs[x][y]=c;
        }
        memset(dp,-1,sizeof(dp)); //Initialize dp as -1, but as 0 is wrongAnswer.
 
        LL ans=0;
        int msk=(1<<n);
        for(int i=0; i<msk; i++)
        {
            for(int j=0; j<n; j++)
            {
                int now=1<<j;
                if(i==0)
                {
                    dp[i|now][j]=a[j];
//                    printf("i=%d p=%d dp[%d][%d]=%d\n",i,j,i,j,dp[i|now][j]);
//                    continue;
                }
                else if(dp[i][j]!=-1)
                {
                    for(int p=0; p<n; p++)
                    {
                        now=1<<p;
                        if(i&now) continue;
                        else
                        {
                            dp[i|now][p]=max(dp[i|now][p],dp[i][j]+a[p]+rs[j][p]);
//                            printf("i=%d p=%d dp[%d][%d]=%d\n",i,p,i|now,p,dp[i|now][p]);
                        }
                    }
//                    int sz=rule[j].size();
//                    for(int p=0; p<sz; p++)
//                    {
//                        int t=rule[j][p].first;
//                        int v=rule[j][p].second;
//                        //                        now=1<<t;
//                        //                        printf("%d %d %d\n",i,1<<j,1<<t);
//                        now=1<<t;
//                        if(i&now) continue;
//                        else
//                        {
//                            dp[i|now][t]=max(dp[i|now][t],dp[i][j]+a[j]+a[t]+v);
//                            //                            printf("i=%d dp[%d]=%d\n",i,state,dp[state]);
//                        }
//                    }
                }
                if(cal(i)==m) ans=max(ans,dp[i][j]);
            }
//            printf("i=%d num=%d dp[%d]=%d\n",i,cal(i),i,dp[i]);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}
 
/*
2 2 2
1 1
2 1 1
1 2 2
 
2 2 0
1 1
 
4 3 2
1 2 3 4
2 1 5
3 4 2
*/