期望dp+高斯消元优化——uvalive4297好题

灰太狼 2021-12-01 16:42 253阅读 0赞

非常好的题！期望+建矩阵是简单的，但是直接套高斯消元会T

所以消元时要按照矩阵的形态 进行优化

#include<bits/stdc++.h>
    using namespace std;
     
    const int maxn = 55;
    const int maxm = 55*55;
    const double esp = 1e-8;
    
    int n,m,r,dir[4][2]={
        {
        1,0},{
        0,1},{-1,0},{
        0,-1}};
    double a[maxm][maxm],b[maxm],p[maxn][maxn][4];
    
    //优化后的高斯消元，考虑矩阵的形态，我们只要求出a[0][0]和b[0]的值
    //并且a[r-1][r-1]和b[r-1]是确定的，那么就可以从r-1行往上消元
    //不断把主元消去即可，主元前面的未知项的系数不用考虑直接修改即可
    //和主元i相关的行只有向上的m行，同时主元所在的行未知项系数也只有m个
    //所以 复杂度为 O(nm^3) 
    double gauss(){
        for(int i=r-1;i>=0;i--){
            int down=max(0,i-m);
            for(int j=i-1;j>=down;j--){
        //一行行往上消元 
                double rate=a[j][i]/a[i][i];
                for(int k=i;k>=down;k--)
                    a[j][k]-=a[i][k]*rate;
                b[j]-=rate*b[i];
            }
        }
        return b[0]/a[0][0];
    }
    
    int main(){
        while(scanf("%d%d",&n,&m),n){
            memset(a,0,sizeof a);
            memset(b,0,sizeof b);
            memset(p,0,sizeof p); 
            
            for(int k=0;k<4;k++)
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++)
                        scanf("%lf",&p[i][j][k]);
            r=n*m;
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++){
                    int id=i*m+j;
                    b[id]=a[id][id]=1;
                    if(i==n-1&&j==m-1)continue;
                    for(int k=0;k<4;k++){
                        int x=i+dir[k][0];
                        int y=j+dir[k][1];
                        if(x<0||x>=n || y<0||y>=m)continue;
                        a[id][x*m+y]-=p[i][j][k];
                    }
                }
            b[r-1]=0;
            printf("%lf\n",gauss());
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11061924.html