hdu 4487 Maximum Random Walk(확률 dp)

제목: 처음에 당신은 원점에서 매번 일정한 확률로 왼쪽으로 한 걸음 가거나 오른쪽으로 한 걸음 가거나 움직이지 않습니다. 지금 요구합니다. n걸음을 가신 후에 가장 오른쪽에 있는 위치에 대한 기대입니다.
사고방식: 사실 간단하다.Σ가장 오른쪽으로 갈 확률.그러면 맨 오른쪽 단점을 일일이 열거하고 확률 dp로 계산하면 됩니다.처음의 상태는 다음과 같다. dp[i][j][k]는 현재 i보를 가야 한다. 이때의 위치는 j이고 남은 노정에서 k를 초과할 확률이 없다.이렇게 하면 모든 매거진의 위치 x에 대해 결과는 x*(dp[n][0][x]-dp[n][0][x-1])를 더해야 한다. 사실 이 복잡도는 이미 지나갈 수 있다. 그러나 나는 sb가 표시를 잘못 해서 시간이 초과되었다. 나는 데이터가 비교적 변태인 줄 알고 생각해 보니 상압이 압축될 수 있다는 것을 발견했다.사실 현재 위치는 중요하지 않다. 우리는 현재 거리 제한의 가장 오른쪽이 얼마나 먼지만 관심을 가진다. 그러면 상태는 dp[i][j]로 쓸 수 있다. 현재 i보를 가야 한다. 이때 거리 제한의 위치의 거리는 j의 확률 0이다.이렇게 하면 복잡도를 O(n^2)로 최적화할 수 있다.dp를 할 때 상태를 바꾸면 더 좋은 복잡도를 얻을 수 있을지도 모른다는 점은 생각해 볼 만하다.
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-6
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const int Base = 100;
double dp[maxn][maxn*2],L,R;
int vis[maxn][maxn*2],T;
double f(int remain,int limit)
{
    if(remain == 0) return 1;
    if(vis[remain][limit] == T) return dp[remain][limit];
    vis[remain][limit] = T;
    double & ans = dp[remain][limit] = 0;
    ans = f(remain - 1,limit + 1)*L + f(remain - 1,limit)*(1.0 - L - R);
    if(limit > 0)
        ans += f(remain - 1,limit - 1)*R;
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t,tcase;
    T = 0;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        T++;
        scanf("%d%d%lf%lf",&tcase,&n,&L,&R);
        double ans = 0;
        for(int i = 1;i <= n;++i)
        {
            ans += (f(n,i) - f(n,i - 1))*i;
        }
        printf("%d %.4lf
",tcase,ans);
    }
    return 0;
}

hdu 4487 Maximum Random Walk(확률 dp)

좋은 웹페이지 즐겨찾기