QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532773#8554. Bot Friendschenxinyang2006WA 98ms10160kbC++202.4kb2024-08-25 11:32:282024-08-25 11:32:28

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 11:32:28]
  • 评测
  • 测评结果:WA
  • 用时:98ms
  • 内存:10160kb
  • [2024-08-25 11:32:28]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n;
char s[5005];

int dp[2][5005][5005],opt[2][5005][5005];
void solve(){
	scanf("%s",s + 1);
	n = strlen(s + 1);
	rep(i,0,n + 1){
		fill(dp[0][i],dp[0][i] + n + 1,-inf);
		fill(dp[1][i],dp[1][i] + n + 1,-inf);
		dp[0][i][i] = dp[1][i][i] = 0;
	}
	rep(len,2,n){
		rep(i,1,n){
			int j = i + len - 1,pl,pr;
			if(j > n) break;
			pl = i;pr = j - 1;
			if(len > 2){
				chkmax(pl,opt[0][i][j - 1]);
				chkmin(pr,opt[0][i + 1][j]);
			}
			rep(k,pl,pr){
				if(dp[0][i][k] + dp[0][k + 1][j] > dp[0][i][j]){
					opt[0][i][j] = k;
					dp[0][i][j] = dp[0][i][k] + dp[0][k + 1][j];
				}				
			}
			pl = i;pr = j - 1;
			if(len > 2){
				chkmax(pl,opt[1][i][j - 1]);
				chkmin(pr,opt[1][i + 1][j]);				
			}
			rep(k,pl,pr){
				if(dp[1][i][k] + dp[1][k + 1][j] > dp[1][i][j]){
					opt[1][i][j] = k;
					dp[1][i][j] = dp[1][i][k] + dp[1][k + 1][j];
				}
			}
			if(s[j] != '>') chkmax(dp[0][i][j],dp[1][i][j - 1] + 1);
			if(s[i] != '<') chkmax(dp[1][i][j],dp[0][i + 1][j] + 1);
//			assert(opt[0][i][j] >= opt[0][i][j - 1] && opt[1][i][j] >= opt[1][i][j - 1]);
//			if(len > 2) assert(opt[0][i][j] <= opt[0][i + 1][j] && opt[1][i][j] <= opt[1][i + 1][j]);
//			printf("[%d,%d] [0]%d [1]%d\n",i,j,dp[0][i][j],dp[1][i][j]);
		}
	}
	int answer = max(dp[0][1][n],dp[1][1][n]);
	rep(i,1,n - 1) chkmax(answer,dp[0][1][i] + dp[1][i + 1][n]);
	printf("%d\n",answer);
}

int main(){	
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10160kb

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 98ms
memory: 10096kb

input:

100000
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
>><>><<<<<
>?>?>?<<>>
?><?<<?<><
???><>?>?>
<??>?<<><?
??>><?<>>>
<><><?<>>?
?>>?>???><
?<?><?<<>?
>>><?<??><
><><<>?>?<
>?><>><<<?
>??>?><?<>
?????<><?>
<><<?<<>?<
><?>>?>?>?
?><><<<>>?
?<>?<>?<<<
<><<<<<>>>
?>?>?><<>>
<>?<>><>?<
<<<?<>>...

output:

8
7
8
5
6
8
7
7
6
7
7
6
8
7
8
7
8
7
7
6
7
7
7
5
7
6
5
9
7
7
5
7
7
9
7
6
8
7
8
8
6
7
6
4
7
7
8
7
9
6
6
6
7
8
8
8
8
7
6
7
7
7
7
8
8
6
8
6
7
8
7
7
7
8
6
7
7
7
5
6
7
8
6
6
8
7
7
7
6
7
7
7
7
8
6
8
9
7
8
7
7
6
8
8
7
6
8
7
7
8
8
7
5
7
8
6
7
7
7
8
8
7
7
8
8
8
8
7
7
8
7
8
7
6
8
6
7
8
7
8
7
7
6
7
7
7
7
7
7
8
...

result:

wrong answer 7th numbers differ - expected: '6', found: '7'