首页 > 代码库 > zoj 3471 Most Powerful

zoj 3471 Most Powerful

2024-07-25 19:15:29   217人阅读

题目链接：zoj 3471 Most Powerful

很经典的状态dp，使用i的二进制位表示粒子的状态，0表示存在，1表示不存在。dp[i]表示在状态i的情况下能够释放的最大的能量，注意自身不能够发生碰撞。例如4个粒子的状态1100表示第0个和第1个粒子不存在，第2、3个粒子存在则可以转移到状态1110或1101。最终遍历只剩下一颗粒子的情况下的所有能量中的最大值。

代码如下：

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 #define     MAXN 11 6 using namespace std; 7 int arr[MAXN][MAXN]; 8 int dp[1<<MAXN]; 9 int n;10 void solve()11 {12     memset(dp, 0, sizeof(dp));13     for( int i = 0 ; i < 1<<n ; i++ )14     {15         for( int j  = 0 ; j < n ; j++ )16         {17             if( ((1<<j) & i) == 0 )18             {19                 for( int k = 0 ; k < n ; k++ )20                 {21                     if( ((1<<k) & i) == 0 && k!= j )22                     {23                         dp[i|(1<<j)]  = max(dp[i|(1<<j)], dp[i] + arr[k][j]);24                     }25                 }26             }27         }28     }29     int ans = 0;30     for( int i = 0 ; i < n ; i++ )31     {32         ans = max(ans, dp[((1<<n)-1)^(1<<i)]);33     }34     printf ( "%d\n", ans );35 }36 int main(int argc, char *argv[])37 {38     while( scanf ( "%d", &n ) && n )39     {40         for( int i = 0 ; i < n ; i++ )41         {42             for( int j = 0 ; j < n ; j++ )43             {44                 scanf ( "%d", &arr[i][j] );45             }46         }47         solve();48     }49 }

 

zoj 3471 Most Powerful


联系
我们