本文共 740 字，大约阅读时间需要 2 分钟。

题目链接：

题目大意：

给出n个物品，选出m个，如果有两个物品存在一条有向边，那么获得这条边的边权，每个点有一个点权，问如何选取能获得最多的权值。

题目分析：

• 因为数据量比较小，所以采用的是状态压缩.
• 定义dp[s][i]表示在状态s（记录某个物品选或没选）下第i个物品作为最后一个选取的物品的最大值，那么转移很简单，就是如果存在有向边，那么就加点权与边权，否则就只加点权。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAX = 1<<19;typedef long long LL;LL dp[MAX][20];int n,m,k;int a[20];int mp[20][20];int main ( ){    while ( ~scanf ( "%d%d%d" , &n , &m , &k ) )    {        memset ( mp , 0 , sizeof ( mp ) );        for ( int i = 0 ; i < n ; i ++ )            scanf ( "%d" , &a[i] );        while ( k-- )        {            int x,y,z;            scanf ( "%d%d%d" , &x , &y , &z );            x--,y--;            mp[x][y] = z;        }        int total = 1<
      
     
    
   

转载地址：http://xqvjn.baihongyu.com/