51nod(1398 등 버스) 기대

10386 단어
51nod 1398 문제: 우리가 하나의 수조 dp[i]를 운전하면 i시간에 차가 출발할 확률이 얼마나 되는지 나타낸다. 우리는 먼저 수조를 dp[s]로 구할 수 있다. 그리고 우리는 i가 s시간보다 작은 dp[i]로 다음 시간이 s시간보다 많을 때 차가 출발할 확률을 구하면 된다. 그리고 그 확률을 한 시간차(i+t[j]-s)에 타고 구체적으로 코드를 실현한다.
#include
using namespace std;
typedef long long LL;
const int maxn=2e5+10;
double dp[maxn];//dp[i]    i            ,         
int n,s;
int t[105],p[105];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&t[i],&p[i]);
        }
        for(int i=0;i<=s;i++){
            dp[i]=0.0;
        }
        dp[0]=1.0;
        for(int i=0;i<=s;i++){
            if(dp[i]==0.0)continue;
            for(int j=1;j<=n;j++){
                double x=p[j],y=100.0;
                dp[i+t[j]]+=(dp[i]*(x/y));
            }
        }
        double res=0.0;
        for(int i=0;i<s;i++){
            for(int j=1;j<=n;j++){
                if(i+t[j]>s){
                    double ko=(i+t[j]-s);
                    double x=p[j],y=100.0;
                    res+=(ko*dp[i]*(x/y));
                }
            }
        }
        printf("%.4f
"
,res); } return 0; }

좋은 웹페이지 즐겨찾기