확률·dp연습(16.04.16)

선배가 낸 세 문제 중 하나는 자신이 예전에 쓴 것이고 박문을 쓴 적이 있기 때문에 본고는 확률과 관련된 간단한 문제를 하나 더 찾아 숫자를 채웠다.

UVA - 12230 Crossing Rivers

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3382대의: 한 사람이 서쪽 기슭에서 동쪽 기슭까지 가면 그 사이에는 많은 강이 있고 사람이 육지에서 걷는 속도는 1이다.강의 매개 변수: p,l,v는 각각 강의 서안 거리 기점 육지의 거리, 강의 너비, 배가 강에서 주행하는 속도를 나타낸다.분석: 배가 강에서 달리는 극단적인 상황: (1)|||||->||||(2)|->||<||-->| 그래서 평균 주행시간은 2l/v 결과: ∑2livi+D - |||||||∑li

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n,d;
    int ca=0;
    while(~scanf("%d%d",&n,&d)){
        if(n==0 && d==0) break;
        double ans=0;
        int p,l,v;
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&p,&l,&v);
            ans=ans+2.0*l/v-l;
        }
        ans=ans+d;
        printf("Case %d: %.3lf

",++ca,ans);
    }
    return 0;
}

hdu 4405 Aeroplane chess

http://acm.hdu.edu.cn/showproblem.php?pid=4405대의: N+1개의 칸이 있는데 0부터 시작하여 매번 집색자, 1-6개의 포인트를 가지고 앞으로 도약한다. >=n점까지 도약한다. 그 중에서 도약점은ai,bi에 대해ai에서 바로bi에 이르기까지 색자를 던지는 개수에 대한 기대를 나타낸다.분석:fork=1–>6:dp[i]=∑(dp[i+k]×16)+1 아날로그 점프, 즉 프로그램의continue.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e3+10,M=2e5+20;
struct node{
    int s,e;
}f[N];
double dp[M];
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<m;i++)  scanf("%d%d",&f[i].s,&f[i].e);
        for(int i=n-1;i>=0;i--){
            bool tag=0;
            for(int j=0;j<m;j++){
                if(f[j].s==i){ dp[i]=dp[f[j].e]; tag=1; break; }
            }
            if(tag) continue;
            for(int j=i+1;j<=i+6;j++) dp[i]+=dp[j]*1.0/6;
            dp[i]++;
        }
        printf("%.4lf
",dp[0]);
    }
    return 0;
}

hdu 5001 walk

http://acm.hdu.edu.cn/showproblem.php?pid=5001대의: 한 폭의 무방향도에 대해 임의의 점에서 출발하여 k보를 걷고 i결점을 거치지 않는 확률을 구한다.분석: dp[i][j]를 설정하는 의미는 i보를 거쳐 j에 도달할 확률이다. 그러면 벡터의 전방향 성폭력에 대해 해답을 구하면 된다.인터넷 코드를 참조하여 AC를 수정한 후의 의혹: 나는 이 문제가 매우 이상하다고 생각한다. 만약에 마지막 d단계에 i점이 포함되지 않았느냐고 묻는다면 처음에 왜 반드시 i점을 뛰어넘어야 합니까?만약 그것이 한 걸음 한 걸음 i점이 포함되지 않는다고 묻는다면, 왜 마지막으로 d걸음이 다른 점에 도달할 확률을 구하는 것이 답입니까? --------------16.04.25 업데이트: d단계를 거치지 않는 점이 있습니다.

//bad code: 
       for(int i=1;i<=n;i++){
            memset(dp,0,sizeof(dp));
            for(int j=1;j<=n;j++) dp[0][j]=1.0/n;
            for(int j=1;j<=d;j++){
                for(int k=1;k<=n;k++){
                    if(k==i) continue;
                    int len=edge[k].size();
                    for(int h=0;h<len;h++){
                        int v=edge[k][h];
                        dp[j][v]+=dp[j-1][v];
                        dp[j][v]+=dp[j-1][k]*1.0/len;
                    }
                }
            }
            printf("%.10lf
",1-dp[d][i]);
        }

비교:

//AC:
        for(int i=1;i<=n;i++){
            memset(dp,0,sizeof(dp));
            for(int j=1;j<=n;j++) dp[0][j]=1.0/n;
            for(int j=1;j<=d;j++){
                for(int k=1;k<=n;k++){
                    if(k==i) continue;
                    int len=edge[k].size();
                    for(int h=0;h<len;h++){
                        int v=edge[k][h];
                        dp[j][v]+=dp[j-1][k]*1.0/len;
                    }
                }
            }
            double ans=0;
            for(int j=1;j<=n;j++) if(j!=i) ans=ans+dp[d][j];
            printf("%.10lf
",ans);
        }

전체 코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
double dp[10005][55];
int main()
{
    //freopen("cin.txt","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,m,d;
        scanf("%d%d%d",&n,&m,&d);
        vector<int> edge[55];
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        for(int i=1;i<=n;i++){
            memset(dp,0,sizeof(dp));
            for(int j=1;j<=n;j++) dp[0][j]=1.0/n;
            for(int j=1;j<=d;j++){
                for(int k=1;k<=n;k++){
                    if(k==i) continue;
                    int len=edge[k].size();
                    for(int h=0;h<len;h++){
                        int v=edge[k][h];
                        dp[j][v]+=dp[j-1][k]*1.0/len;
                    }
                }
            }
            double ans=0;
            for(int j=1;j<=n;j++) if(j!=i) ans=ans+dp[d][j];
            printf("%.10lf
",ans);
        }
    }
    return 0;
}