我发现我其实也不是会dp,就是心里上感觉很难,然后做题的时候就认为很难,就不去分析,然后老是看别人的题解。。。。以后一定要好好分析再写啊!
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> #include<stack> #include<vector> #include<climits> using namespace std; #define ll __int64 #define rep(i,n) for(i=0; i<(n); i++) #define reph(i,n,m) for(i=(n); i<=(m); i++)//正循环的 #define repd(i,n,m) for(i=(n); i>=(m); i--) //负循环的 #define fab(a) (a)>0?(a):0-(a) #define arc(a) (a)*(a) #define inf 100000000 //最大值的 #define exp 0.0000001 //浮点型的 #define N 10 double a[N][N]; double sum[N][N][N][N]; double dp[15][N][N][N][N]; int n; int main() { int i,j,k,l,r,tot; double m,temp; while(scanf("%d",&n)!=EOF) { reph(i,1,8) reph(j,1,8) scanf("%lf",&a[i][j]); memset(sum,0,sizeof(sum)); //计算和的 reph(i,1,8) reph(j,1,8) { reph(k,i,8) { reph(l,j,8) { m=0; reph(r,i,k) { m+=a[r][l]; } sum[i][j][k][l]=sum[i][j][k][l-1]+m; } } } double average=sum[1][1][8][8]/n; reph(i,1,8) reph(j,1,8) reph(k,i,8) reph(l,j,8) { sum[i][j][k][l]*=sum[i][j][k][l]; dp[0][i][j][k][l]=sum[i][j][k][l]; } reph(tot,1,n-1) reph(i,1,8) reph(j,1,8) { reph(k,i,8) reph(l,j,8) { temp=inf; reph(r,i,k)//横着的 temp=min(temp,min(dp[tot-1][i][j][r][l]+sum[r+1][j][k][l],dp[tot-1][r][j][k][l]+sum[i][j][r-1][l])); reph(r,j,l) temp=min(temp,min(dp[tot-1][i][r][k][l]+sum[i][j][k][r-1],dp[tot-1][i][j][k][r]+sum[i][r+1][k][l])); dp[tot][i][j][k][l]=temp; } } average=dp[n-1][1][1][8][8]/n-average*average; printf("%0.3lf\n",sqrt(average)); } return 0; }