1875

11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int n, ans;
int a[N];
int f1[N], f[N];

int main()
{
cin >> n;

ans = 0;

for(int i = 1; i <= n; i ++ )
scanf("%d", a + i);

for(int i = 1; i <= n; i ++ )
{
f[i] = 1;

for(int j = 1; j < i; j ++ )
if(a[i] > a[j])
f[i] = max(f[i], f[j] + 1);

}

for(int i = n; i >= 1; i --)
{
f1[i] = 1;

for(int j = n; j > i; j -- )
if(a[i] > a[j])
f1[i] = max(f1[i], f1[j] + 1);

}

for(int i = 1; i <= n; i ++ )
{
ans = max(ans, f[i] + f1[i] - 1);
}

cout << n - ans << endl;

return 0;
}


11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int n, ans;
int a[N];
int f1[N], f[N];

int main()
{
cin >> n;

ans = 0;

for(int i = 1; i <= n; i ++ )
scanf("%d", a + i);

for(int i = 1; i <= n; i ++ )
{
f[i] = 1;

for(int j = 1; j < i; j ++ )
if(a[i] > a[j])
f[i] = max(f[i], f[j] + 1);

}

for(int i = n; i >= 1; i --)
{
f1[i] = 1;

for(int j = n; j > i; j -- )
if(a[i] > a[j])
f1[i] = max(f1[i], f1[j] + 1);

}

for(int i = 1; i <= n; i ++ )
{
ans = max(ans, f[i] + f1[i] - 1);
}

cout << ans << endl;

return 0;
}


11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int t, n;
int a[N], dp[N];

int main()
{
cin >> t;

while(t -- )
{
cin >> n;

for(int i = n; i >= 1; i -- )
{
scanf("%d", a + i);
dp[i] = INF;
}

for(int i = 1; i <= n; i ++ )
{
*lower_bound(dp + 1, dp + n + 1, a[i]) = a[i] ;
}

auto ans = lower_bound(dp + 1, dp + n + 1, INF) - dp - 1 ;

for(int i = n; i >= 1; i -- )
{
dp[i] = INF;
}

for(int i = n; i >= 1; i -- )
{
*lower_bound(dp + 1, dp + n + 1, a[i]) = a[i] ;
}

ans = max(ans, lower_bound(dp + 1, dp + n + 1, INF) - dp - 1 );

cout << ans << endl;

}

return 0;
}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 110000;

ll n, ans;
int a[N], b[N];

void merge_sort(int l, int r)
{
if(l >= r) return;

int mid = l + r >> 1;

merge_sort(l, mid), merge_sort(mid + 1, r);

int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
else b[k ++ ] = a[j ++ ];
while(i <= mid) b[k ++ ] = a[i ++ ];
while(j <= r) b[k ++ ] = a[j ++ ];

for(int i = l, j = 0; i <= r; i ++, j ++  )
a[i] = b[j];

}

int main()
{

cin >> n;

for(int i = 0; i < n; i ++ )
scanf("%d", a + i);

merge_sort(0, n - 1);

for(int i = 0; i < n - 1; i ++ )
cout << a[i] << " ";
cout << a[n - 1] << endl;

return 0;

}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 110000;

ll n, ans;
int a[N], b[N];

void merge_sort(int l, int r)
{
if(l >= r) return;

int mid = l + r >> 1;

merge_sort(l, mid), merge_sort(mid + 1, r);

int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
else {
ans += mid - i +  1;
b[k ++ ] = a[j ++ ];
}
while(i <= mid) b[k ++ ] = a[i ++ ];
while(j <= r) b[k ++ ] = a[j ++ ];

for(int i = l, j = 0; i <= r; i ++, j ++  )
a[i] = b[j];

}

int main()
{

cin >> n;

for(int i = 0; i < n; i ++ )
scanf("%d", a + i);

merge_sort(0, n - 1);

cout << ans << endl;

return 0;

}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 31;

int n, m;
int f[N][N];

int main()
{

cin >> n >> m;

if(n % 2 == 0 && m % 2 == 0)
cout << "0" << endl;
else
{
f[1][1] = 1;
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= m; j ++ )
{
if(i == 1 && j == 1 )
continue;
if(i % 2 != 0 || j % 2 != 0)
{
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}

// for(int i = 1; i <= n; i ++ )
// {
//     for(int j = 1; j <= m; j ++ )
//         cout << f[i][j] <<  " ";
//         cout << endl;
// }

cout << f[n][m] << endl;

}

return 0;

}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string s;

int main()
{

cin >> s;

for(int i = 0; i < s.length(); i ++ )
{
if(s[i] >= '0' && s[i] <= '9')
{
for(int j = 1; j < s[i] - '0'; j ++ )
cout << s[i - 1];
}
else
cout << s[i];
}

cout << endl;

return 0;

}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

ll n;

int main()
{

cin >> n;

int flag = 0;

while(n)
{
if(flag == 0)
{
flag = 1;
cout << n;
}
else
{
cout << " " << n;
}
n /= 2;
}

cout << endl;

return 0;

}


28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m, t;
PII a[N];
int v[N];
int last[N];
bool st[N];

int main()
{

cin >> n >> m >> t;

for(int i = 1; i <= m; i ++ )
{
scanf("%d%d", &a[i].first, &a[i].second);
}

sort(a + 1, a + 1 + m);

// for(int i = 1; i <= m; i ++ )
// {
//     cout << a[i].first << " " << a[i].second << endl;
// }

for(int i = 1; i <= m; )
{
int j = i;
while (j <= m && a[j] == a[i]) j ++ ;
int id = a[i].second;
int tim = a[i].first;
int cnt = j - i;
i = j;

v[id] -= tim - last[id] - 1;
if(v[id] < 0) v[id] = 0;
if(v[id] <= 3) st[id] = false;

v[id] += 2 * cnt;
if(v[id] > 5) st[id] = true;

last[id] = tim;
}

int ans = 0;

for(int i = 1; i <= n; i ++ )
if(t > last[i] && (v[i] - (t - last[i])) <= 3)
st[i] = false;

for(int i = 1; i <= n; i ++ )
if(st[i])
ans ++;

cout << ans << endl;

return 0;

}



29天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;

int l, n, m, flag;
char g[N][N][N];
bool st[N][N][N];
int dist[N][N][N];

struct node{
int z, x, y;
};

int kk[6][3] = {{0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}};

node a, b;

void bfs()
{
queue<node> q;
q.push({a.z, a.x, a.y});
dist[a.z][a.x][a.y] = 0;
st[a.z][a.x][a.y] = true;

while(!q.empty())
{
node t = q.front();
q.pop();

if(t.x == b.x && t.y == b.y && t.z == b.z)
{
cout << "Escaped in "  << dist[t.z][t.x][t.y] << " minute(s)."<< endl;
flag = 1;
break;
}

for(int i = 0; i < 6; i ++ )
{
int tx = t.x + kk[i][0];
int ty = t.y + kk[i][1];
int tz = t.z + kk[i][2];

// cout << tx << " " << ty << " " << tz << endl;

// cout << l << " " << n << " " << m << endl;

if(tx >= 0 && ty >= 0 && tz >= 0 && tx < n && ty < m && tz < l && g[tz][tx][ty] != '#' && st[tz][tx][ty] == false)
{
// cout << tx << " " << ty << " " << tz << endl;
q.push({tz, tx, ty});
st[tz][tx][ty] = true;
dist[tz][tx][ty] = dist[t.z][t.x][t.y] + 1;
}

}

}

}

int main()
{

while(cin >> l >> n >> m && n, m, l )
{

flag = 0;

memset(st, false, sizeof st);
memset(dist, 0, sizeof st);

for(int i = 0; i < l; i ++ )
{
for(int j = 0; j < n; j ++ )
scanf("%s", g[i][j]);
}

for(int i = 0; i < l; i ++ )
for(int j = 0; j < n; j ++ )
for(int k = 0; k < m; k ++ )
if(g[i][j][k] == 'S')
{
a.z = i;
a.x = j;
a.y = k;
}
else if(g[i][j][k] == 'E')
{
b.z = i;
b.x = j;
b.y = k;
}

bfs();

if(flag == 0)
cout << "Trapped!" << endl;

}

return 0;

}