[HDU5492]Find a path

题目大意：
　　一个n*m的格子，每个格子上都有一个数。
　　你可以向下或者向右走，从(1,1)走到(n,m)，问方差*(n+m-1)最小的路径是哪个？

思路：
　　方差*(n+m-1)就相当于给格子里每个数乘上(n+m-1)再求方差。
　　由于数据范围较小，我们可以直接枚举每个平均数，再求一条方差最小的路径。
　　不用担心平均数和所走的路径不对应的情况。
　　因为就算这次的平均数和路径不对应，我们还是可以再下一次枚举到正确的平均数，而用正确的平均数算的方差显然是更小的。

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int inf=0x7fffffff;

 const int N=,M=;

 int a[N][M],f[N][M];

 int n,m;

 inline int sqr(const int &x) {

     return x*x;

 }

 inline void dp(const int &avg) {

     std::fill(&f[][],&f[n][m+],inf);

     f[][]=sqr(a[][]*(n+m-)-avg);

     for(register int i=;i<=n;i++) {

         for(register int j=;j<=m;j++) {

             f[i+][j]=std::min(f[i+][j],f[i][j]+sqr(a[i+][j]*(n+m-)-avg));

             f[i][j+]=std::min(f[i][j+],f[i][j]+sqr(a[i][j+]*(n+m-)-avg));

         }

     }

 }

 int main() {

     const int T=getint();

     for(register int i=;i<=T;i++) {

         printf("Case #%d: ",i);

         n=getint(),m=getint();

         for(register int i=;i<=n;i++) {

             for(register int j=;j<=m;j++) {

                 a[i][j]=getint();

             }

         }

         int ans=inf;

         for(register int i=;i<=;i++) {

             dp(i);

             ans=std::min(ans,f[n][m]/(n+m-));

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

[HDU5492]Find a path

最新文章

热门文章