#include<iostream>#include<sstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>using namespace std;const double eps(1e-8);typedef long long lint;#define clr(x) memset( x , 0 , sizeof(x) )#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clrs( x , y ) memset( x , y , sizeof(x) )const int Maxn = 2010;int n;lint f[Maxn][Maxn], sum[Maxn], x[Maxn];int g[Maxn][Maxn];bool v[Maxn][Maxn];vector <int> ret[Maxn];vector <int> tmp;void Dfs(int l, int r) { if (v[l][r]) return; v[l][r] = true; if (l + 1 == r) { f[l][r] = sum[r] - sum[l - 1]; g[l][r] = l; return; } if (l == r) { g[l][r] = 0; f[l][r] = 0; return; } Dfs(l, r - 1); Dfs(l + 1, r); f[l][r] = -1; for (int i = g[l][r - 1]; i <= g[l + 1][r]; i ++) { if (i < l) continue; if (i > r - 1) continue; Dfs(l, i); Dfs(i + 1, r); if (f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1] < f[l][r] || f[l][r] == -1) { f[l][r] = f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1]; g[l][r] = i; } } }void Search(int l, int r) { if (l == r) { ret[l] = tmp; return; } tmp.push_back(0); Search(l, g[l][r]); tmp.pop_back(); tmp.push_back(1); Search(g[l][r] + 1, r); tmp.pop_back();}int main() { while (scanf("%d", &n) == 1) { sum[0] = 0; for (int i = 1; i <= n; i ++) { scanf("%lld", &x[i]); sum[i] = sum[i - 1] + x[i]; } memset(v, 0, sizeof(v)); Dfs(1, n); tmp.clear(); Search(1, n); for (int i = 1; i <= n; i ++) { for (int j = 0; j < (int)ret[i].size(); j ++) printf("%d", ret[i][j]); printf("n"); } } return 0;}
