QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #636360 | #9454. String of CCPC | ucup-team191# | AC ✓ | 190ms | 50704kb | C++23 | 811b | 2024-10-12 23:35:40 | 2024-10-12 23:35:41 |
Judging History
answer
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int N = 2e5 + 500;
string s;
int dp[N][5][8], n;
int f(int x, int kol, int msk) {
if(dp[x][kol][msk] != -1) return dp[x][kol][msk];
int ret = 0;
if(kol < 4) ret = max(ret, max(f(x, kol + 1, (2 * msk) & 7) + (msk == 1), f(x, kol + 1, (2 * msk + 1) & 7)) - kol);
if(x == n) return max(ret, 0);
ret = max(ret, f(x + 1, kol, (2 * msk + (s[x] == 'P')) & 7) + (s[x] == 'C' && (msk == 1)));
return dp[x][kol][msk] = ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
for(;T--;) {
cin >> n >> s;
for(int i = 0;i <= n;i++) {
for(int j = 0;j < 5;j++)
for(int t = 0;t < 8;t++)
dp[i][j][t] = -1;
}
cout << f(0, 0, 7) << '\n';
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
3 3 CCC 5 CCCCP 4 CPCP
output:
1 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 190ms
memory: 50704kb
input:
20003 5 PCCPC 10 CPPPPCPCPC 4 CPPC 11 CCPPCPPPCCP 17 PPPPCPCCCCCPCCCCC 10 PPCCPCPPCP 9 CPCCCCPPC 11 PCPPPPCCPPP 15 CPCPPPPCCPCPCCC 11 PCCPPCCPCPP 9 PCPCCPPCP 10 CCPCPPPCPP 14 CCCCPPPCPCPCPP 2 CC 12 CCPCPPPPPCPP 6 CPPPPP 12 PCCPCCCCCPCC 16 CPCCPCCPPCCCCPPC 7 CPPPCPC 16 PPPPPCCPCPCPCPPC 13 PPPCPCCCCPP...
output:
1 1 0 1 2 1 1 1 2 2 1 1 1 0 1 0 3 2 1 2 1 2 2 0 1 2 3 1 1 3 1 2 2 1 0 0 0 3 1 0 0 1 1 2 0 1 1 0 1 2 0 1 0 1 0 3 1 1 0 2 1 3 2 2 0 2 2 0 0 2 1 1 3 3 1 3 1 2 0 1 1 0 1 2 2 1 1 2 1 3 1 1 3 1 2 2 0 1 0 3 0 1 1 2 2 0 2 1 1 2 2 0 3 1 1 1 1 2 1 2 0 1 1 0 3 0 3 1 1 0 0 1 0 3 0 1 1 1 1 2 2 1 1 0 0 1 2 0 1 2 ...
result:
ok 20003 lines
Extra Test:
score: 0
Extra Test Passed