题解 | #[NOIP2008]传纸条#

问题描述：略。

转移方程：

状态表示：

​ F(k,i,j)，k表示一共走了多少步，i和j表示两个传递坐标的横坐标。通过k - i + 1, k - j + 1可以确定两个坐标的纵坐标。

​ 对于(k,i,j)的状态是由

这四种进行传递来的。

​ 同时由于不能经过相同的坐标。因此我设置一个横坐标不相等来做。（感觉有点小错误

AC代码（：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e2 + 21;
int f[N][N][N], g[N][N];
void inpfile();
void solve() {
    int n,m; cin>>n>>m;
    rep(i,1,n) {
        rep(j,1,m) cin>>g[i][j];
    }
    rep(k,1,n + m - 1) {
        rep(i,1,n) {
            rep(j,1,i-1) {
                int ii = k - i + 1;
                int jj = k - j + 1;
                if(ii < 1 || jj < 1) continue;
                f[k][i][j] = max({ f[k-1][i][j], f[k-1][i-1][j-1], f[k-1][i][j-1], f[k-1][i-1][j]}) + g[i][ii] + g[j][jj];
            }
        }
    }
    cout<<f[n + m - 1][n][n - 1];

}
int main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}