C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 616K, 提交时间: 2020-06-23 22:40:44

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
#define int long long 
int cnt[10][2]; int ans; int n, m, k;
void dfs(int x, int y, int now, int p) {
	if (x > n || y > m) return;
	if (x == n && y == m) {
		ans = max(p, ans);
		return;
	}
	for (int i = now + 1; i <= k; i++) {
		for (int j = 1; j <= 100; j++) {
			int c = x + cnt[i][0]*j;
			int d = y + cnt[i][1]*j;
			if (c > n || d > m) break;
			dfs(c, d, i, p + 1);	
		}
	}
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m >> k; ans = 0;
		for (int i = 1; i <= k; i++) {
			string s; cin >> s;
			int x = 0, y = 0;
			for (int j = 0; j < s.size(); j++) {//记录每种行走方式能走的距离
				if (s[j] == 'U') y++;
				else x++;
			}
			cnt[i][0] = x; cnt[i][1] = y;
		}
		dfs(0, 0, 0, 0);
		cout << ans << endl;
	}
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 722ms, 内存消耗: 56660K, 提交时间: 2020-06-22 16:37:54

for _ in range(int(input())):
	n, m, k = map(int, input().split())
	n += 1
	m += 1
	dp = [[[0]*(1<<5) for i in range(101)] for j in range(101)]
	delta = [[0]*2 for i in range(5)]
	dp[0][0][0] = 1
	for kk in range(k):
		x = input()
		dx, dy = 0, 0
		for xx in x:
			if xx=='R':
				dx += 1
			else:
				dy += 1
		delta[kk][0], delta[kk][1] = dx, dy
	for i in range(n):
		for j in range(m):
			for mask in range(1<<k):
				for kk in range(k):
					prei, prej = i - delta[kk][0], j - delta[kk][1]
					if prei>=0 and prej>=0 and prei<n and prej<m:
						dp[i][j][mask|(1<<kk)] |= dp[prei][prej][mask]
	ans = 0
	for mask in range(1<<k):
		bit = 0
		for i in range(k):
			if (mask>>i)&1:
				bit += 1
		if bit>ans and dp[n-1][m-1][mask]:
			ans = bit
	print(ans)

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 616K, 提交时间: 2020-06-23 15:37:30

#include<bits/stdc++.h>
using namespace std;

int n,m,k,ans,dx[5],dy[5],Max[105][105];
void DFS(int x,int y,int z)
{
	int i,j,X,Y,Z;
	if(x==n&&y==m)return;
	for(i=0;i<k;i++)
	{
		X=x+dx[i],Y=y+dy[i],Z=z|(1<<i),j=__builtin_popcount(Z);
		if(X<=n&&Y<=m&&j>Max[X][Y])Max[X][Y]=j,DFS(X,Y,Z);
	}
}
int main()
{
    int i,j,T;
    char R[5][105];
    scanf("%d",&T);
    while(T--)
    {
    	scanf("%d%d%d",&n,&m,&k);
    	memset(dx,0,sizeof(dx)),memset(dy,0,sizeof(dy));
    	for(i=0;i<k;i++)scanf("%s",R[i]);
    	for(i=0;i<k;i++)
    	    for(j=0;R[i][j]!='\0';j++)
    	    {
    	    	if(R[i][j]=='R')dx[i]++;
			    else dy[i]++;
			}
    	memset(Max,0,sizeof(Max)),DFS(0,0,0);
    	printf("%d\n",Max[n][m]);
	}
}