有n（n<10）个小球，每两个碰撞有其中一个会消失，并产生一定能量。求产生最大能量。

有了正确思路题目比较简单，我的思路果然是歪的。。。

 

我的思路是dp[i][j]表示i这个状态剩下第j个小球，然后转移方程：

dp[j|(1<

感觉没什么问题，但是WA了好多好多次呢！

知道自己怎么错的是个大事。。。。。。。。。

因为这样每次都是用碰撞过的小球来碰撞，但是其实比如有四个小球 1和2碰撞 3和4碰撞 然后剩下的两个在碰撞，这样的情况更新不到。

 

副ac代码吧，写的也很挫。。。

#include 
     
      #include 
      
       using namespace std;const int N = 11;const int MAXN = 1 << N;int dp[MAXN];int power[N][N];int main(){    int n;    while (cin >> n && n)    {        for (int i = 0; i < n; ++i)        {            for (int j = 0; j < n; ++j)            {                cin >> power[i][j];            }        }        int st = (1 << n) - 1;        memset(dp, 0, sizeof dp);        for (int s = 0; s <= st; ++s)        {            for (int i = 0; i < n; ++i)            {                if (((1 << i) & s) == 0)                for (int j = 0; j < n; ++j)                {                    if (((1 << j) & s) == 0)                    {                        if (i != j)                        {                            dp[s | (1 << i)] = max(dp[s | (1 << i)], dp[s] + power[j][i]);                        }                    }                }            }        }        int ans = 0;        for (int s = 0; s <= st; ++s)            ans = max(ans, dp[s]);        cout << ans << endl;    }}