QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554363 | #8554. Bot Friends | ucup-team1231# | TL | 292ms | 3964kb | C++14 | 2.1kb | 2024-09-09 10:42:53 | 2024-09-09 10:42:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
typedef long long int LLI;
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
char s[5001];
int dp[2][5001][2];
int pre[10005],suff[10005];
int main() {
int i,j,k;
int T,n;
scanf("%d",&T);
while (T--) {
scanf("%s",s);
n = strlen(s);
auto f = [&](int *arr) {
for (i = 0; i <= n; i++) dp[0][i][0] = dp[0][i][1] = 1e9;
dp[0][1][1] = 0;
arr[0] = 0;
for (i = 1; i <= 2*n; i++) {
for (j = 0; j <= n; j++) {
for (k = 0; k < 2; k++) dp[i & 1][j][k] = 1e9;
}
for (j = 0; j <= n; j++) {
for (k = 0; k < 2; k++) {
if (dp[(i-1) & 1][j][k] < 1e9) {
if (i & 1) {
if (s[(i-1)/2] != '>') {
if (j > 0) dp[i&1][j-1][0] = min(dp[i&1][j-1][0],dp[(i-1)&1][j][k]+k);
}
if (s[(i-1)/2] != '<') {
if (j < n) dp[i&1][j+1][1] = min(dp[i&1][j+1][1],dp[(i-1)&1][j][k]);
}
}
else {
if (j > 0) dp[i&1][j-1][0] = min(dp[i&1][j-1][0],dp[(i-1)&1][j][k]+k);
if (j < n) dp[i&1][j+1][1] = min(dp[i&1][j+1][1],dp[(i-1)&1][j][k]);
}
}
}
}
arr[i+1] = dp[i & 1][0][0];
}
};
f(pre);
reverse(s,s+n);
for (i = 0; i < n; i++) {
if (s[i] == '<') s[i] = '>';
else if (s[i] == '>') s[i] = '<';
}
f(suff);
reverse(suff,suff+2*n+1);
int ans = 1e9;
for (i = 0; i <= 2*n; i += 2) {
ans = min(ans,pre[i]+suff[i]);
}
printf("%d\n",n-ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 292ms
memory: 3964kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 8 6 7 6 7 6 6 8 7 8 7 8 7 7 6 6 7 7 2 6 6 3 9 6 6 5 7 5 8 7 6 8 7 8 6 6 7 4 2 7 6 8 7 8 6 6 5 7 8 8 8 8 7 5 6 7 7 6 8 8 6 8 6 7 8 7 7 6 8 5 7 6 6 5 5 7 7 6 4 8 6 6 7 5 7 6 7 7 8 3 8 8 7 8 7 7 4 8 8 7 5 8 7 7 8 8 7 5 7 8 5 7 6 5 8 8 7 7 8 6 7 8 6 6 8 7 8 7 6 6 5 7 8 6 8 6 7 5 7 4 6 6 7 7 7 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 280ms
memory: 3808kb
input:
100000 <<<<>>>>>< >>>><<<><< >><?>><<<< <><><<>?<> ><>?>>?<>< <<<<><><>< >>>??<><>< <<><?>?<<< >?<<<><<<< <<>><<><>< <>?<<<<>>< >>?>>>><>> ?>><<?<<<< >>>><><??< ><<<<<><<< ><???<>><> <<<<><<<>> ?<>>?>?<<< <><>><><>> <>><<<<>>< <<>><<<<>> ><><<<<?<< ><<<<<><>> >>>><<><?> ><>>?><?<< ??<?<??<<? <<<<><<...
output:
2 8 8 5 7 3 7 6 6 5 6 4 8 8 4 6 2 8 4 6 4 6 3 7 8 8 3 4 5 7 5 8 7 6 5 6 5 5 6 6 5 7 3 4 7 6 6 5 8 7 5 3 6 4 6 6 3 4 6 6 8 6 6 6 7 4 4 6 6 6 1 5 4 7 6 5 6 4 4 4 5 5 4 6 8 7 4 6 4 4 5 4 7 8 6 6 6 6 4 7 5 6 4 6 6 7 4 2 5 5 6 5 6 6 5 6 4 4 3 8 5 7 5 6 6 6 5 5 7 8 7 5 4 4 5 6 7 5 3 5 5 3 7 7 2 7 6 8 7 2 ...
result:
ok 100000 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
100000 >>>??><<>?<>??>><>?< >><<>????<<<>?>>?<<< <>>??><><>>?>>?><>?> <<<<><>><>>>???>>>?< <>>>?<>>>?<><??<<<>> >><><><><?<>>><>??>< >?<>?????<?<<><<<<>> ?><<>?>??>>>??<><<?< >>><>?<?>>?<?<??>?>< <>>?<<?>???><?><><>? <>?<?>?>?<>?<????>?< <??<>?<>><<?<?????<< >?>?<><>?<><><>>>??> >?<??>?<??>>>>><><?<...
output:
15 17 12 12 14 13 15 17 15 14 15 15 13 16 15 16 15 15 17 15 15 10 16 12 14 16 17 16 11 14 13 14 13 14 14 10 12 11 15 13 16 13 13 13 16 10 14 16 12 12 13 14 14 16 17 13 15 15 11 17 15 15 16 15 17 15 16 14 14 13 11 15 14 17 15 17 17 15 13 17 16 16 16 14 17 14 12 14 13 15 16 12 15 16 14 15 13 16 15 14 ...