区间DP C++ 求调
查看原帖
区间DP C++ 求调
764455
HAPPYspider楼主2024/6/2 23:57

一直输出nan,找不到问题
代码如下

#include<bits/stdc++.h>
using namespace std;

double sigma;
int n;
int num[10][10];
int sum[10][10];
double dp[20][10][10][10][10];//dp[i][x1][y1][x2][y2]

long long Getsum(int x1,int y1,int x2,int y2){
    //cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}

long long Sum(int x1,int y1,int x2,int y2){
    double D=double(Getsum(x1,y1,x2,y2));
    D=D*D;
    D=D/double(n);
    //cout<<D<<endl;
    return D;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            scanf("%d",&num[i][j]);
            sigma+=double(num[i][j]);
            sum[i][j]=num[i][j];
        }
    }
    sigma=sigma/double(n);
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
        }
    }
    for(int i=1;i<n;i++){
        for(int x2=8;x2>=1;x2--){
            for(int y2=8;y2>=1;y2--){
                for(int x1=x2-1;x1>=1;x1--){
                    for(int y1=y2-1;y1>=1;y1--){
                        dp[i][x1][y1][x2][y2]=INT_MAX;
                        for(int k=x1;k<=x2;k++){
                            dp[i][x1][y1][x2][y2]=min(dp[i][x1][y1][x2][y2],min(dp[i-1][x1][y1][k][y2]+Sum(k+1,y1,x2,y2),dp[i-1][k+1][y1][x2][y2]+Sum(x1,y1,k,y2)));
                        }
                        for(int k=y1;k<=y2;k++){
                            dp[i][x1][y1][x2][y2]=min(dp[i][x1][y1][x2][y2],min(dp[i-1][x1][y1][x2][k]+Sum(x1,k+1,x2,y2),dp[i-1][x1][k+1][x2][y2]+Sum(x1,y1,x2,k)));
                        }
                    }
                }
            }
        }
    }
    cout<<dp[n-1][1][1][8][8]<<endl;
    printf("%.3lf",sqrt(dp[n-1][1][1][8][8]-(sigma*sigma)));
    return 0;
}
2024/6/2 23:57
加载中...