codevs 1997 守卫者的挑战

/*
表示很遗憾..
开始状态想的没错 就是转移的时候出了问题 自己也想到了数组平移
然而没往下写 与正解擦肩而过….
然后为了好转移写了个4维的 时间不多了没来得及降维 草草的算算空间就交了…
尼玛double忘记*8了 华丽的直接Memory limit exceeded while compiling
我尼玛0分
考试后写了写用原来的状态写了写数组平移然后降维
数据太水就A了 */
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 210
#define base 200
using namespace std;
int n,l,K,p[maxn],c[maxn],sum;
double f[][maxn*][maxn],ans;
int main()
{
scanf("%d%d%d",&n,&l,&K);sum+=K;
for(int i=;i<=n;i++)scanf("%d",&p[i]);
for(int i=;i<=n;i++)
{
scanf("%d",&c[i]);
if(c[i]!=-)sum+=c[i];
}
f[][K+base][]=;
for(int i=;i<=n;i++)
{
for(int j=sum+base;j>=;j--)
for(int k=n;k>=;k--)
{
if(k>&&j>=c[i])f[i&][j][k]+=f[(i-)&][j-c[i]][k-]*(double(p[i])/100.0);//赢了
f[i&][j][k]+=f[(i-)&][j][k]*(double(-p[i])/100.0);//输了
}
for(int j=sum+base;j>=;j--)
for(int k=n;k>=;k--)
f[(i-)&][j][k]=;
}
for(int i=base;i<=sum+base;i++)
for(int j=l;j<=n;j++)
ans+=f[n&][i][j];
printf("%.6f\n",ans);
return ;
}
上一篇:PTA 数组循环右移


下一篇:IDL 数组相关函数