DFS水題URAL 1152 False Mirrors
7984 ワード
テーマゲート
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 }