CF 1728 D. Letter Picking 区间dp 1800

CF 1728 D. Letter Picking 区间dp 1800,第1张

题意:一个长度为 n 并且 n 是偶数的非空字符串 s,Alice 有字符串 a,Bob有字符串 b,最初都是空的,从 Alice 开始轮流从 s 字符串的开头或者结尾取一个字符,移到自己的字符串的开头。最后谁的字符串大谁有赢,如果相等就平局。求对于每个字符串 s,游戏的结果是什么。

思路:区间 dp,dp[l][r] 表示从字符串 sl 到 sr-1 开始游戏最后的结果。-1表示Alice获胜,0表示平局,1表示Bob获胜。那么答案就是 dp[0][n]。因为每一轮取的字符要放在开头,所以后面轮次取的字母在更前面,所以当前这一轮的结果要从后一轮转移过来,从当前轮一人取一个字符有三种情况:开头和结尾一人取一个;两人都在开头取;两人都在结尾取;取完的结果分别是:dp[l + 1][r - 1] ; dp[l + 2][r] ; dp[l][r - 2]。对于 Bob 来说,Alice先手从一端选择一个字符后,Bob可以选择另一端,也可以选择同一端,也就是说Bob可以保证自己选到第一种情况。也可以选到第二种情况和第三种情况中的一种,而具体是哪一种是由 Alice 控制的。所以当前轮的结果应该是max(dp[l + 1][r - 1] , min(dp[l + 2][r], dp[l][r - 2]));但是要注意,三种情况中的平局,结果不一定是平局,要根据当前轮选择的字符来判断。

代码:

#include
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 2e5 + 10, P = 1e9 + 7, mod = 998244353;
int dp[2010][2010];
void solve() {
	string s;
	cin >> s;
	int n = s.size();
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++) dp[i][j] = 0;
	for(int len = 2; len <= n; len += 2) {
		for(int l = 0; l + len <= n; l++) {
			int r = l + len;
			int res = -1, res1 = -1, res2 = -1; 
			
			if(dp[l + 1][r - 1]) res = max(res, dp[l + 1][r - 1]);
			else if(s[l] == s[r - 1]) res = 0;
			
			if(dp[l + 2][r]) res1 = max(res1, dp[l + 2][r]);
			else {
				if(s[l] == s[l + 1]) res1 = 0;
				if(s[l] < s[l + 1]) res1 = 1;
			}
			
			if(dp[l][r - 2]) res2 = max(res2, dp[l][r - 2]);
			else {
				if(s[r - 1] == s[r - 2]) res2 = 0;
				if(s[r - 1] < s[r - 2]) res2 = 1;
			}
			dp[l][r] = max(res, min(res1, res2));
 		}
	}
	if(dp[0][n] == -1) cout << "Alice" << endl;
	else if(!dp[0][n]) cout << "Draw" << endl;
	else cout << "Bob" << endl;
}                
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int tt = 1;
	cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/2889506.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-14
下一篇 2022-09-14

发表评论

登录后才能评论

评论列表(0条)

保存