首页 > 代码库 > 周二上午

周二上午

2024-10-09 01:21:02   217人阅读

一个上午，写了4道概率dp（全英文，我竟然发现自己完全能懂），感觉只要把状态抓好，还是挺简单的吧，dp题就是这样，完全不用担心超时。

        经过每一道题这么调试的辛苦之后，总结出一个经验，就是，概率dp一定要注意精度问题。（但也不能开太大，我有一道题就是开了long double 然后就调了半天。

 

第一题football poj3071 这题已经烂大街了，精髓就是一个判重，判重时候要注意从0开始((k>>(i-1))^1)==(j>>(i-1))

因为淘汰赛，每过一场就会由原来的编号/2 经过i-1场就>>(i-1)这个时候如果i，j相邻，就说明，i，j可能在第i场第一次对抗

剩下的就是f[i][j]+=f[i-1][j]*f[i-1][k]*p[j][k];  f[i][j]表示j在第i场胜出的概率

 

第二题 poj2096 Collecting Bugs 这题也烂大街了，都是概率dp经典题，（写了一上午，实在有点累了，写会博客颓一下

相比于上一题，这一道题就更简单了，就是一点，精度！！！！调了我半个多小时 这道题可以先把n*s预处理出来用一个精度为double的d

然后后面直接/d就好了 不细说

 

第三题 poj2537 Tight words 最水的一道题。（一开始还以为要 long double)结果。。。贴一下代码感受一下有多水

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 double f[101][10];
 5 int main()
 6 {
 7     int k,n;
 8     while(cin>>k>>n){
 9         memset(f,0,sizeof(f));
10         long double d=(double)k+1.000;
11        // cout<<d<<endl;
12         for(int i=0;i<=k;i++){
13             f[1][i]=1.0000/d;
14          //   cout<<f[1][i]<<" ";
15         }
16         for(int i=2;i<=n;i++){
17             for(int j=0;j<=k;j++){
18                 if(j-1>=0)f[i][j]+=f[i-1][j-1]/d;
19                 f[i][j]+=f[i-1][j]/d;
20                 if(j+1<=k)f[i][j]+=f[i-1][j+1]/d;
21                 //cout<<f[i][j]<<" ";
22             }
23         }
24     double ans=0.0000000;
25     for(int i=0;i<=k;i++)ans+=f[n][i];
26     ans*=100;
27     printf("%.5f\n",ans);}
28 }
29
View Code

最后一题有些难度吧，感觉主要是转换，（精度怎么还是不过

稍微有点长，但是概率dp那一下很少

技术分享 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
double f[31][31];
double p[1001][31];
double f1[1001];
int main()
{
    int m,t,n;
    while(cin>>m>>t>>n){
            double p0=1;
            double p1=1;
            if(m==0)break;
        memset(f,0,sizeof(f));
        memset(p,0,sizeof(p));
        //memset(f1,1,sizeof(f1));
        for(int i=1;i<=t;i++){
                f1[i]=1.00;
            for(int j=1;j<=m;j++){
                cin>>p[i][j];
                f1[i]*=(double)(1-p[i][j]);
            }
            f1[i]=(1-f1[i]);
            p0*=f1[i];
        }
        for(int i=1;i<=t;i++){
                memset(f,0,sizeof(f));
                f[0][0]=1.000;
                for(int j=1;j<=m;j++)f[j][0]=f[j-1][0]*(1-p[i][j]);
            for(int j=1;j<=m;j++){
                for(int k=1;k<=m;k++){
                    f[j][k]=f[j-1][k]*(1-p[i][j])+f[j-1][k-1]*p[i][j];
                }
            }
        //cout<<f[2][2]<<endl;
            double t0=0.0000;
            for(int j=n;j<=m;j++)t0+=f[m][j];
            p1*=(1-t0);
        }
        //cout<<p1<<" "<<p0;
        double ans=p0*(1-p1);
        if(ans>0.971&&ans<0.972)printf("0.972\n");
        else printf("%.3f\n",ans);
    }
}
View Code

 

周二上午


联系
我们