HDU5569/BestCoder Round #63 (div.2) C.matrix DP

时间:2023-03-08 21:51:50
HDU5569/BestCoder Round #63 (div.2) C.matrix    DP

matrix

Problem Description
Given a matrix with n rows and m columns ( n+m is an odd number ), at first , you begin with the number at top-left corner (1,1) and you want to go to the number at bottom-right corner (n,m). And you must go right or go down every steps. Let the numbers you go through become an array a1,a2,...,a2k. The cost is a1∗a2+a3∗a4+...+a2k−1∗a2k. What is the minimum of the cost?
Input
Several test cases(about 5)

For each cases, first come 2 integers, n,m(1≤n≤1000,1≤m≤1000)

N+m is an odd number.

Then follows n lines with m numbers ai,j(1≤ai≤100)

Output
For each cases, please output an integer in a line as the answer.
Sample Input
2 3
1 2 3
2 2 1
2 3
2 2 1
1 2 4
Sample Output
4
8
题解:令dp[i][j]dp[i][j]表示当前走到第i,ji,j个位置的最小贡献,我们可以假定(i+j)(i+j)为奇数,由该状态可以转移向最多44个位置,就可以了。
///
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>
#include <stack>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define meminf(a) memset(a,127,sizeof(a)); inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//****************************************
#define maxn 100000+50
#define mod 1000000007
#define inf 1000000007 ll a[][],b[maxn],k,dp[][],l[maxn],r[maxn],ans[maxn],D[maxn],n,m;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=n;i++) {
for(int j=;j<=m;j++) {
scanf("%I64d",&a[i][j]);dp[i][j]=inf;
}
}
dp[][]=;
for(int i=;i<=n;i++) {
for(int j=;j<=n;j++) {
if(i==&&j==) {
dp[i][j+]=min(dp[i][j]+a[i][j]*a[i][j+],dp[i][j+]);
dp[i+][j] =min( dp[i][j]+a[i][j]*a[i+][j],dp[i+][j]);
}
else {
dp[i][j+]=min(dp[i][j]+a[i][j+]*a[i][j+],dp[i][j+]);
dp[i+][j] =min( dp[i][j]+a[i+][j]*a[i+][j],dp[i+][j]);
dp[i+][j+]=min(dp[i][j]+a[i+][j]*a[i+][j+],dp[i+][j+]);
dp[i+][j+] =min( dp[i][j]+a[i][j+]*a[i+][j+],dp[i+][j+]);
}
}
} cout<<dp[n][m]<<endl; } return ;
}