思路:一开始看到这题的时候想DP，可是发现貌似不行。。因为有前缀也有后缀，而且有的后缀会覆盖到现在的前缀，这就不满足无后效性了啊！
但是有个很巧妙的思路:如果我们知道a[i]的最大值，那么p的数量和q的数量也确定了。所以序列长度也确定了，设m为序列长度。
而且对于每个a[i]都代表了一个固定数量的p和q和长度。
因此，长度大于m/2的前缀，我们可以用总的p和总的q减去它，转换成小于等于m/2长度的前缀后缀。
这样我们可以设计DP为f[i][j][k],代表从左往右i个中有j个p，从右往左i个有k个p，这样f[(m+1)/2]的位置就是最终答案!
注意要记录一个pre数组记录这个状态的最优解是从哪个位置转移过来的。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
ll a[];
const ll PW=;
const ll QW=;
int c[][],n,pre[][][][],w[][],f[][][];
int ans[],cn;
int read(){
char ch=getchar();int t=,f=;
while (ch<''||''<ch){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void init(){
n=read();
for (int i=;i<n;i++){
double x;scanf("%lf",&x);
a[i]=(ll)(x*+0.5);
}
}
void solve(){
int mxpos=;
for (int i=;i<n;i++){
if (a[i]>a[mxpos]) mxpos=i;
}
int totp=-,totq=-;
for (int i=;(ll)i*PW<=a[mxpos];i++)
if ((a[mxpos]-(ll)i*PW)%QW==){
totp=i;
totq=(int)((a[mxpos]-(ll)i*PW)/QW);
break;
}
for (int i=;i<n;i++){
int p=-,q=-;
for (int j=;(ll)j*PW<=a[i];j++)
if ((a[i]-(ll)j*PW)%QW==){
p=j;
q=(int)((a[i]-(ll)j*PW)/QW);
break;
}
if (p!=-&&p+q<=totp+totq){
c[cn][]=p;
c[cn][]=q;
cn++;
}
}
int m=totp+totq;
for (int i=;i<cn;i++){
if (c[i][]+c[i][]<=m/){
w[c[i][]+c[i][]][c[i][]]++;
}else{
w[m-c[i][]-c[i][]][totq-c[i][]]++;
}
}
f[][][]=;
for (int i=;i<=m/;i++)
for (int j=;j<=i;j++)
for (int k=;k<=i;k++){
int s=-;
for (int p=;p<=;p++){
for (int q=;q<=;q++){
if (j-p>=&&j-p<i&&k-q>=&&k-q<i&&f[i-][j-p][k-q]>s){
s=f[i-][j-p][k-q];
pre[i][j][k][]=p;
pre[i][j][k][]=q;
}
}
}
f[i][j][k]=s+w[i][j]+((k==j)?:w[i][k]);
}
int ansi=-,ansj=-,ansk=-;
for (int k=;k<=m%;k++)
for (int i=;i<=m/;i++){
int j=totq-k-i;
if (j>=&&j<=m/&&(ansi==-||f[m/][i][j]>f[m/][ansi][ansj])){
ansi=i;
ansj=j;
ansk=k;
}
}
if (m%) ans[m/]=ansk;
for (int i=m/;i>;i--){
int p=pre[i][ansi][ansj][];
int q=pre[i][ansi][ansj][];
ans[i-]=p;
ans[m-i]=q;
ansi-=p;
ansj-=q;
}
for (int i=;i<m;i++)
if (ans[i]) printf("Q");
else printf("P");
}
int main(){
init();
solve();
}