UVA10081 Tight Words(dp)

Given is an alphabet {0,1,…,k}, 0 ≤ k ≤ 9. We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1. Input Input is a sequence of lines, each line contains two integer numbers k and n, 1 ≤ n ≤ 100. Output For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, …, k} with 5 fractional digits. Sample Input 41 25 35 87 Sample Output 100.00000 40.74074 17.38281 0.10130
제목의 뜻: 한 줄의 길이는 n이고 0~k의 숫자로 구성되어 있다.그리고 두 숫자에 인접한 모든 차이의 절대값은 1보다 크지 않다.이 요구에 부합되는 수는 모든 길이가 n인 수의 백분율을 차지한다.
사고: 가장 간단한 상황, 1개의 수, 2개의 수, 3개의 수부터 생각하자...그래서 정의: 길이가 i인 tight words는 f[i]개가 있다.그러나 f[i]를 결정하는 요소는 i위 자체가 얼마인지, 그리고 i-1위의 수가 얼마인지를 발견하고 2차원 상태로 정의할 생각이다.f[i][j]는 i위가 j일 때 길이가 i인 tightwords가 몇 개인지 나타낸다.방정식: f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1];경계 조건: f[1][j]=1;(0<=j<=k); 정답: f[n][0-k]의 합.주의해야 할 것은 백분율을 요구하기 때문에 분모(k+1)^n을 직접 계산하면 너무 크지만 계산을 거친 분자는 저장할 수 있다는 것이다.그래서 먼저 dp로 분자를 계산한 다음에 끊임없이 k를 나누면 된다.하지만!!가장 중요한 것은 정밀도 문제!!!!
이것은 첫 번째 출력 방법으로 f[i][j]가 정의한 정수로tot를 계산할 때 더블로 전환하여 k를 나눈다

const double EPS=1e-9;
typedef long long LL;
typedef unsigned long long ULL;
ULL f[105][15],n,k;
int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>k>>n)
    {
        mem(f);
        for(int i=0;i<=k;i++) f[1][i]=1;
        for(int i=2;i<=n;i++)
            for(int j=0;j<=k;j++)
                if (j>0) f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1];
                else f[i][j]=f[i-1][j]+f[i-1][j+1];
        double tot=0;       
        for(int i=0;i<=k;i++) tot+=f[n][i]; 
            k++;
         for(int i=1;i<=n;i++)
             tot=((double) (tot*EPS))/((double) (k*EPS));
    //  n=pow(k+1,n);
        printf("%.5lf
",(double)(tot)*100.0);
    //  printf("%.5lf
",((double) (tot*EPS))/((double) (n*EPS))*100.0);        
    }
    return 0;
}

이것은 ac의 문법이다. f[i][j]는 더블로 저장하고 추가할 때 끊임없이 k를 제외하고 마지막에 더블로 정의된tot를 더하면 된다.

const double EPS=1e-9;
typedef long long LL;
typedef unsigned long long ULL;
ULL n,k;
double f[110][15];
int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>k>>n)
    {
        mem(f);
        for(int i=0;i<=k;i++) f[1][i]=1.0;
        for(int i=2;i<=n;i++)
            for(int j=0;j<=k;j++)
                if (j>0) f[i][j]=1.0/(k+1)*(f[i-1][j-1]+f[i-1][j]+f[i-1][j+1]);
                else f[i][j]=1.0/(k+1)*(f[i-1][j]+f[i-1][j+1]);
        double tot=0.0;     
        for(int i=0;i<=k;i++) tot+=1.0/(k+1)*(f[n][i]); 
    //  n=pow(k+1,n);
        printf("%.5lf
",tot*100.0);
    //  printf("%.5lf
",((double) (tot*EPS))/((double) (n*EPS))*100.0);        
    }
    return 0;
}

그중의 현학은 스스로 깨달아야 한다qwq...