如果贡献为a[i]，大家都会求，而现在变成了乘积的和，怎么求呢？
首先我们观察到n+m为奇数，所以我们可以想到右对角线（左上到右下）。
通过找规律，我们发现，当i+j为奇数时，我们走了偶数步，这时加上乘积（上一步的值*这一步的值）；
当i+j为偶数时，我们走了奇数步，这时不需要更新值，就从可以来到这个点的点中取一个min转移过来就行了。
注意：
min和max包含在algorithm库中，在HDU上必须加上头文件。
1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 #include<cstdio> 5 #include<algorithm> 6 using namespace std; 7 int n,mm; 8 int m[1005][1005],dp[1005][1005]; 9 int main(){ 10 while(scanf("%d%d",&n,&mm)!=EOF){ 11 memset(dp,0x3f,sizeof(dp)); 12 memset(m,0x3f,sizeof(m)); 13 for(int i=1;i<=n;i++){ 14 for(int j=1;j<=mm;j++){ 15 scanf("%d",&m[i][j]); 16 } 17 } 18 dp[1][1]=0; 19 for(int i=1;i<=n;i++){ 20 for(int j=1;j<=mm;j++){ 21 if(i==1&&j==1) continue; 22 if((i+j)&1){ 23 if(i-1>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+m[i-1][j]*m[i][j]); 24 if(j-1>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+m[i][j-1]*m[i][j]); 25 }else{ 26 dp[i][j]=min(dp[i-1][j],dp[i][j-1]); 27 } 28 } 29 } 30 cout<<dp[n][mm]<<endl; 31 } 32 return 0; 33 }
原文：https://www.cnblogs.com/yinyuqin/p/12215542.html