很久以前写过的一道DP题
当时不会DP 也是想了蛮久233
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// <message.cpp> - 02/29/16 22:12:20 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int a[201][201],f[51][51][51][51]; int main(){ freopen("message.in","r",stdin); freopen("message.out","w",stdout); int m=getint(),n=getint(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)a[i][j]=getint(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=m;k++) for(int l=1;l<=n;l++){ if(j==l||i==k)continue; f[i][j][k][l]=a[i][j]+a[k][l]+max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])); } printf("%d",max(f[m][n-1][m-1][n],f[m-1][n][m][n-1])+a[m][n]); return 0; } |