AcWing 275 传纸条 题解 （动态规划—DP—线性DP）

题目
详细思路见方格取数

#include

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N][N];

int main()
{
	cin>>n>>m;
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= m; j ++ ){
			cin>>w[i][j];
		}
	}
	
	for(int k = 2; k <= n + m; k ++ ){
		for(int i1 = max(1, k - m); i1 <= min(k - 1, n); i1 ++ ){
			for(int i2 = max(1, k - m); i2 <= min(k - 1, n); i2 ++ ){
				int j1 = k - i1, j2 = k - i2;
					int &x = f[k][i1][i2];
					int t = w[i1][j1];
					if(i1 != i2) t += w[i2][j2];
					x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
					x = max(x, f[k - 1][i1 - 1][i2] + t);
					x = max(x, f[k - 1][i1][i2 - 1] + t);
					x = max(x, f[k - 1][i1][i2] + t);
				} 
		}
	}
	cout<