CF580D Kefa and Dishes 【状压dp】By cellur925

友情链接：new2zydalao%%% 一篇优秀的状压文章

题目大意：$n$个菜有$k$个规则，如果kefa在吃完第$x_i$个菜之后吃了第$y_i$个菜（保证$x_i$、$y_i$不相等）,

那么会额外获得$c_i$ (0<=$c_i$<=$10^9$)(0<=$c_i$<=$10^9$)的满意度。（0<$n$<=18）.但是他希望自己吃菜的顺序得到的满意度最大，

请你帮帮kefa吧！

数据范围这么小==，应该会用到状压的。但是之前状压都是那些比较明显的在棋盘上的类型，这种完全布吉岛如何设计状态及转移。

上次做的类似题是NOIp2017宝藏。其实感觉这种题有一个（较）固定的思路：设$f[i][j]$表示当前状态为$i$，目前在$j$。这次我们可以如出一辙，设$f[i][j]$表示为当前状态为$i$，最后吃的一道菜为$j$获得的最大满意度。

好啦。有了状态，转移就不难了。我们枚举当前状态以及当前吃的最后一个菜，再枚举吃的上一个菜，那么显然有方程$f[i][j]=$max(f[i^(1<<i)][k]+a[j]+w[j][k])$。注意一下细节及初值就行了，感觉本题并没有太难==。

$Code$

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n,m,qwq;

 ll ans,a[],f[][],w[][];

 int count(int x)

 {

     int tmp=;

     while(x)

         tmp+=(x&),x>>=;

     return tmp;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&qwq);

     for(int i=;i<n;i++) scanf("%lld",&a[i]),f[(<<i)][i]=a[i];

     for(int i=;i<=qwq;i++)

     {

         ll x=,y=;

         scanf("%lld%lld",&x,&y);

         scanf("%lld",&w[x-][y-]);

     }

     int fAKe=(<<n)-;

     for(int i=;i<=fAKe;i++)

     {

         int sum=count(i);

         for(int j=;j<n;j++)

         {

             if(!(i&(<<j))) continue;

             for(int k=;k<n;k++)

             {

                 if(!(i&(<<k))||k==j) continue;

                 f[i][j]=max(f[i][j],f[i^(<<j)][k]+w[k][j]+a[j]);

             }

             if(sum==m) ans=max(ans,f[i][j]);

         }

     }

     printf("%lld",ans);

     return ;

 }

本题中还运用到了一个小技巧（和sjtdalao学的）。位运算我们都知道从0开始搞，那么有时我们为了方便书写，把给出的元素从0~n-1进行标号，符合二进制的传统，就比较舒服。

巴特西

CF580D Kefa and Dishes 【状压dp】By cellur925

最新文章

热门文章