| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 11575 | 2014-12-02T14:16:49 Z | gs14004 | 수열 (BOI14_sequence) | C++ | 0 ms | 0 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
long long res = 1e16, p[17];
void solve(vector<int> bit, long long cb, int depth, int had_zero){
if(cb >= res) return;
if(bit.size() == 1){
int r = bit[0];
if(r == 0){
if(cb == 0 || had_zero) cb += p[depth];
}
else if(r == 1){
cb += p[depth] * 10;
}
else{
if(r&1){
int minima = 1e9;
for (int i=9; i; i--) {
if((r>>i)&1) minima = i;
}
for (int i=9; i; i--) {
if((r>>i)&1 && i != minima){
cb += p[depth] * i;
depth++;
}
}
depth++;
cb += p[depth] * minima;
}
else{
for (int i=9; i; i--) {
if((r>>i)&1 && i != minima){
cb += p[depth] * i;
depth++;
}
}
}
}
res = min(res,cb);
return;
}
for (int i=0; i<10; i++) {
int gz = 0;
vector<int> v2;
int piv = i;
v2.push_back(0);
for (int j=0; j<bit.size(); j++) {
if(bit[j]&1 && piv == 0) gz = 1;
v2.back() |= (bit[j] & (~(1<<piv)));
if(piv == 9 && j != bit.size() - 1){
v2.push_back(0);
piv = -1;
}
piv++;
}
solve(v2,cb + p[depth] * i,depth+1,gz);
}
}
int main(){
vector<int> v;
scanf("%d",&n);
p[0] = 1;
for (int i=1; i<17; i++) {
p[i] = p[i-1] * 10;
}
for (int i=0; i<n; i++) {
int t;
scanf("%d",&t);
v.push_back(1<<t);
}
solve(v,0,0,0);
printf("%lld",res);
}