Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 91 Accepted Submission(s): 62
题解：dp题，发现自己对于dp太弱了。。。
题意是一个n*m的矩阵，从（1，1）走到（n,m）的a1*a2+a3*a4+a5*a6。。。。其中a1,a2。。。是矩阵的当前值；
由于只能向右向下，从（1，1）开始，那么(x+1,y)或（x,y+1）由于是从1+1=2偶数开始，所以到x+y+1是奇数的时候再进行运算，
所以每次往前推两步即可，初始化dp为INF，因为求最小值，dp[1][1]=0；状态转移方程：
if((i+j)&1){
dp[i][j]=min(dp[i-1][j]+num[i-1][j]*num[i][j],dp[i][j-1]+num[i][j-1]*num[i][j]);
}
else dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const int MAXN=1010;
int dp[MAXN][MAXN],num[MAXN][MAXN];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
mem(dp,INF);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&num[i][j]);
if(i==1&&j==1){
dp[i][j]=0;continue;
}
if((i+j)&1){
dp[i][j]=min(dp[i-1][j]+num[i-1][j]*num[i][j],dp[i][j-1]+num[i][j-1]*num[i][j]);
}
else dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
}
printf("%d\n",dp[n][m]);
}
return 0;
}
原文：http://www.cnblogs.com/handsomecui/p/4984909.html