DFS水題URAL 1152 False Mirrors

 1 /*  2    ：   ，      ，              ，           3      ：sum         ，tot       ，     ans ，  ，       4       ，     ，    。         ，        :)  5 */  6 #include <cstdio>  7 #include <algorithm>  8 #include <cstring>  9 #include <cmath> 10 #include <iostream> 11 using namespace std; 12 13 const int MAXN = 25; 14 const int INF = 0x3f3f3f3f; 15 int a[MAXN]; 16 bool vis[MAXN]; 17 int n, ans; 18 19 void DFS(int sum, int tot) 20 { 21 if (tot >= ans) return ; 22 if (sum == 0) {ans = min (ans, tot); return ;} 23 24 for (int i=1; i<=n; ++i) 25  { 26 if (!vis[i]) 27  { 28 vis[i] = true; 29 int s1 = (i == 1) ? n : i - 1; 30 int s2 = (i == n) ? 1 : i + 1; 31 if (vis[s1]) s1 = 24; 32 if (vis[s2]) s2 = 24; 33 vis[s1] = true; vis[s2] = true; 34 sum -= a[s1]; sum -= a[s2]; sum -= a[i]; 35 36 tot += sum; 37  DFS (sum, tot); 38 tot -= sum; 39 40 sum += a[s1]; sum += a[s2]; sum += a[i]; 41 vis[s1] = false; vis[s2] = false; vis[i] = false; 42  } 43  } 44 } 45 46 int main(void) //URAL 1152 False Mirrors 47 { 48 //freopen ("N.in", "r", stdin); 49 50 while (scanf ("%d", &n) == 1) 51  { 52 int sum = 0; a[24] = 0; 53 for (int i=1; i<=n; ++i) {scanf ("%d", &a[i]); sum += a[i];} 54 memset (vis, false, sizeof (vis)); 55 56 ans = INF; DFS (sum, 0); 57 printf ("%d
", ans); 58  } 59 60 return 0; 61 }