题解 CF24D 【Broken robot】

· · 题解

一道高斯消元+dp的好(例)题

But

这不是重点（滑稽.jpg）

-------------------------------------------重点的分割线-----------------------------------------

反复dp就可以做完的题为什么要高斯消元呢？？

(才不是因为我高斯消元写炸了还懒得改)

上状态转移方程(拍黑版！！)：

f_{i,j} =\begin{cases}\frac {f_{i,j}+f_{i+1,j}}{2}+1 , & \text {如果$m=1$}\\ \frac {f_{i+1,j}+f_{i,1}+f_{i,2}}{3}+1, & \text {如果$j=1$ } \\ \frac {f_{i+1,m}+f_{i,m}+f_{i,m-1}}{3}+1, & \text {如果$j=m$ } \\ \frac {f_{i+1,j}+f_{i,j}+f_{i,j+1}+f_{i,j-1}}{4}+1 & \text {其它} \end{cases}

我写的真好 (得意.jpg)

考虑到反复横跳的可能不会太大（坂本参上！）， 而且只要精确到小数点后4~5位（真的）， 为什么不循环个50来次呢？

不就是慢一点吗？2s的时限虚什么？？

实测结果

tips:勿抄题解，人人有责

Code

#include<cstdio>
double dp[1005][1005]；
int main(){
    register int n,m,x,y,i,j,t；
    scanf("%d%d%d%d",&n,&m,&x,&y)；
    for(i=n-1;i>=x;--i)
        for(t=1;t<=50;++t)//循环50次就好
            if(m==1)
                dp[i][1]=(dp[i][1]+dp[i+1][1])/2.0+1；
            else{
                dp[i][1]=(dp[i][1]+dp[i][2]+dp[i+1][1])/3.0+1；
                dp[i][m]=(dp[i][m]+dp[i][m-1]+dp[i+1][m])/3.0+1；
                for(j=2;j<m;++j)
                    dp[i][j]=(dp[i][j]+dp[i][j-1]+dp[i][j+1]+dp[i+1][j])/4.0+1；
            }
    printf("%.5lf\n",dp[x][y])；//本人实测可过！
    return 0；
}

蒟蒻的第一篇题解还请见谅（手动求赞）