QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #633195 | #9454. String of CCPC | ucup-team5071# | AC ✓ | 142ms | 4616kb | C++20 | 2.1kb | 2024-10-12 14:45:31 | 2024-10-12 14:45:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=2e5+10;
int dp[8][2],dp2[8][2];
int ans[100][10];
int solve()
{
int n;cin>>n;
string s;
// string s(n,'C');
cin>>s;
s="x"+s;
vector<int> a(n+1);
for(int i=1;i<=n;i++)a[i]=(s[i]=='P');
for(int j=0;j<8;j++){
for(int k=0;k<2;k++)dp[j][k]=-inf;
}
dp[7][0]=0;
auto gmax = [&](int &x,int y){
if(y>x)x=y;
};
for(int i=1;i<=n;i++){
for(int j=0;j<8;j++){
for(int k=0;k<2;k++)dp2[j][k]=-inf;
}
for(int j=0;j<8;j++){
for(int k=0;k<=1;k++){
// cout<<"i="<<i<<" j="<<j<<" k="<<k<<" dp="<<dp[i-1][j][k]<<endl;
if(k==0){
for(int ins=0;ins<2;ins++){
for(int c1=0;c1<2;c1++){
int g=j;
string ss="0";
ss[0]+=c1;
ss.insert(ss.begin()+ins,a[i]+'0');
for(auto &it:ss)g=g*2+it-'0';
int res=ans[g][5]+dp[j][k];
int now=g&7;
gmax(dp2[now][k+1],res);
}
}
}
gmax(dp2[(j&3)*2+a[i]][k],dp[j][k]+((j*2+a[i])==2));
}
}
memcpy(dp,dp2,sizeof(dp));
}
int ans=0;
for(int i=0;i<8;i++){
for(int j=0;j<2;j++)gmax(ans,dp[i][j]-max(0,j-1));
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
auto cal = [&](string &s){
int cnt=0;
for(int i=0;i+3<s.size();i++)cnt+=(s.substr(i,4)=="0010");
return cnt;
};
for(int i=0;i<100;i++){
for(int len=1;len<=7;len++){
string s(len,'0');
for(int j=0;j<len;j++)s[j]+=(i>>j&1);
reverse(s.begin(),s.end());
ans[i][len]=cal(s);
}
}
int T;cin>>T;while(T--)cout<<solve()<<"\n";
}
/*
3
3
CCC
5
CCCCP
4
CPCP
1
5
CCCCP
*/
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
input:
3 3 CCC 5 CCCCP 4 CPCP
output:
1 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 142ms
memory: 4616kb
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