【题解】洛谷P4853[非酋yyf的sif之旅]C.yyf hates dagequ 期望DP
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e3+10;
int n,score,judge,minn,maxn;
double P[65][10],per[2][N][6],f[2][N][6],ans,add[65];
//f[i][j][k]表示第i个节奏打了j个combo之后k个节奏改判的期望得分
//per[i][j][k]表示转移到f[i][j][k]的概率
bool to[2][N][6];
//to[i][j][k]表示f[i][j][k]是否转移过
struct node{
int c,p,t;//c次概率p%持续t
bool operator <(const node&rhs)const{
return t>rhs.t;}
}gai[N];
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&score,&judge);
int c,p,s;
for(int i=1;i<=score;i++)
{
scanf("%d%d%d",&c,&p,&s);//c次概率p%加s分
for(int j=c;j<=60;j+=c)
add[j]+=1.000000*(double)(p*s)/100.000000;//当连击数为j时期望加分
}
for(int i=1;i<=judge;i++)
scanf("%d%d%d",&gai[i].c,&gai[i].p,&gai[i].t);
sort(gai+1,gai+judge+1);P[0][0]=1.0;
for(int i=1;i<=60;i++)//60是1~5的lcm
{
double a=1.000000;
for(int j=1;j<=judge;j++)
{
if(i%gai[j].c)continue;
P[i][gai[j].t]+=a*(double)gai[j].p/100.000000;
//combo为i时使用长度为gai[j].c的改判的概率大小
a=(a*(double)(100-gai[j].p))/100.000000;//没有用
}
P[i][0]=a;//没有效果的概率
}
to[0][0][0]=1;per[0][0][0]=1.000000;
for(int i=0,o=1,t=0;i<n;i++)
{
//t的状态转移到o的状态
int po;maxn=0;
scanf("%d",&po);//第i次击打的原始结果
memset(f[o],0,sizeof(f[o]));
memset(per[o],0,sizeof(per[o]));
memset(to[o],0,sizeof(to[o]));
for(int j=0;j<=minn;j++)
for(int k=0;k<6;k++)
{
if(!to[t][j][k])continue;//没有转移过
int co=(j+(po+k>=2))*(po>1||(k&&po));//combo数
int sp=(co-1)%60+1;//得到combo数对应循环节中位置
for(int l=0;l<6;l++)
{
if(!P[sp][l])//combo为sp,长度为l
continue;
int m=(k-1)>l?(k-1):l;//最长持续时间
int poi=min(2,po+(k>0&&po));//改判后的结果
f[o][co][m]+=(f[t][j][k]+(add[sp]+(double)(co+1)*poi)*per[t][j][k])*1.000000*P[sp][l];
per[o][co][m]+=per[t][j][k]*P[sp][l];
to[o][co][m]=1;
maxn=max(maxn,co);
}
}
minn=maxn;swap(o,t);
}
for(int i=0;i<=n;i++)
for(int j=0;j<6;j++)
ans+=f[n&1][i][j];
printf("%.6f\n",ans);
return 0;
}
总结
当时没有做第三题。这个期望DP还是比较厉害的，有很多需要注意的地方和优化。阿福又学会了新招。