n个阳台，每个阳台上有怪物，第一个阳台跟最后一个相邻，每次攻击其中一个阳台，那么相邻的两个也会被破坏掉，但是你攻击一次，剩下的没有被消灭的怪兽就会攻击你，问消灭所有怪兽 所受伤害值最少是多少
一开始就想到了DFS，于是写了一发，居然超时了，然后看到n只有20，于是想到了状态压缩+记忆化搜索，还是比较清晰的推起来，然后31ms过了，后来过了又去看了一下网上题解，呵呵，发现 dfs也是可以的，自己没写好，连基础的东西都忘了。。。
int n;int nnum[20 + 5];int dp[(1<<20) + 5];void init() { memset(nnum,0,sizeof(nnum)); memset(dp,-1,sizeof(dp));}bool input() { while(cin>>n) { for(int i=0;i<n;i++)cin>>nnum[i]; return false; } return true;}int dfs(int ss) { if(dp[ss] != -1)return dp[ss]; int now = 0; for(int i=0;i<n;i++) if(ss &(1<<i)) now += nnum[i]; int ret = inf; for(int i=0;i<n;i++) { int tmp = ss; int sum = 0; int cur = (i + n)%n; if(ss & (1<<cur)) { sum += nnum[cur]; tmp ^= (1<<cur); } cur = (i + n + 1)%n; if(ss & (1<<cur)) { sum += nnum[cur]; tmp ^= (1<<cur); } cur = (i + n - 1)%n; if(ss & (1<<cur)) { sum += nnum[cur]; tmp ^= (1<<cur); } if(tmp == ss)continue; ret = min(ret,dfs(tmp) + now - sum); } return dp[ss] = ret;}void cal() { dp[0] = 0; int ans = dfs((1<<n) - 1); cout<<ans<<endl;}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;}