526互联

CF 570E - Pig and Palindromes

发布时间 2023-06-10 15:23:42作者: hellozhangjz

https://codeforces.com/problemset/problem/570/E
双向DP，类似于摘樱桃：https://leetcode.cn/problems/cherry-pickup/
记忆化搜索，超内存

#include <vector>
#include <string>
#include <functional>
#include <iostream>
using namespace std;

int main()
{
	int n, m, MOD = 1e9+7;

	cin >> n >> m;
	vector<string> g(n);
	for(auto &s:g)
		cin >> s;

	vector<vector<vector<int>>> dp((n+m)/2, vector<vector<int>>(n, vector<int>(n, -1)));
	vector<vector<int>> dir = {{0,0}, {0,-1}, {1,-1}, {1,0}};

	function<int(int, int, int)> ms = [&](int k, int x1, int x2)
	{
		int y1 = k-x1, y2 = m-1-(k - (n-1-x2));
		if(x1 >= n || y1 >= m || x2 < 0 || y2 < 0)
			return -1;

		if(g[x1][y1] != g[x2][y2])
			return dp[k][x1][x2] = 0;
		if(dp[k][x1][x2] != -1)
			return dp[k][x1][x2];

		// 递归基
		if((n+m)%2 && 2*k+1 == m+n-2) // n+m奇数
			return dp[k][x1][x2] = (abs(x1-x2)+abs(y1-y2) == 1 ? 1 : 0);
		else if((n+m)%2==0 && 2*k == m+n-2) // n+m偶数
			return dp[k][x1][x2] = (x1==x2 && y1==y2);

		long long res = 0;

		for(auto &d:dir)
			res = (res + max(0, ms(k+1, x1+d[0], x2+d[1])))%MOD;

		return dp[k][x1][x2] = res;
	};
	cout << ms(0, 0, n-1);
	return 0;
}

改编出的滚动数组版本的dp，通过

#include <vector>
#include <string>
#include <functional>
#include <iostream>
using namespace std;

int main()
{
	int n, m, MOD = 1e9+7;

	cin >> n >> m;
	vector<string> g(n);
	for(auto &s:g)
		cin >> s;

	vector<vector<vector<int>>> dp(2, vector<vector<int>>(n+1, vector<int>(n+1, 0)));

	int k = (n+m)%2 ? (m+n-3)/2 : (m+n-4)/2+1;
	bool indx = false;
	for(int x1 = 0; x1 < n; ++x1)
	{
		int y1 = k-x1;
		if(y1 >= m || y1 < 0)
			continue;
		for(int x2 = n-1; x2 >= 0; --x2)
		{
			int y2 = m-1-(k - (n-1-x2));
			if(y2 >= m || y2 < 0 || x2 < x1 || y2 < y1)
				continue;
			
			dp[indx][x1][x2] = (g[x1][y1] == g[x2][y2]);
		}
	}

	indx = !indx;

	while(k--)
	{
		for(auto &p : dp[indx])
			fill(p.begin(), p.end(), 0);
		for(int x1 = 0; x1 < n; ++x1)
		{
			int y1 = k-x1;
			if(y1 >= m || y1 < 0)
				continue;
			for(int x2 = n-1; x2 >= 0; --x2)
			{
				int y2 = m-1-(k - (n-1-x2));
				if(y2 >= m || y2 < 0 || x2 < x1 || y2 < y1 || g[x1][y1] != g[x2][y2])
					continue;
				
				dp[indx][x1][x2] = (dp[indx][x1][x2] + dp[!indx][x1][x2])%MOD;
				dp[indx][x1][x2] = (dp[indx][x1][x2] + dp[!indx][x1+1][x2])%MOD;
				dp[indx][x1][x2] = (dp[indx][x1][x2] + (x2-1 >= 0 ? dp[!indx][x1][x2-1] : 0))%MOD;
				dp[indx][x1][x2] = (dp[indx][x1][x2] + (x2-1 >= 0 ? dp[!indx][x1+1][x2-1] : 0))%MOD;
			}
		}
		indx = !indx;
	}
	indx = !indx;
	cout << dp[indx][0][n-1];
	return 0;
}