asp网站防攻击,音乐展示网站建设平台,saas软件,2016网站设计欣赏P7928 [COCI2021-2022#1] Kamenčići
题目大意
小 A A A和小 B B B在玩游戏。在他们面前#xff0c;有 n n n块石头排成一行#xff0c;石头有红和蓝两种颜色。
小 A A A先手#xff0c;每次每人从两段中的一段取出一块石头#xff0c;谁先取出 k k k块石头谁就输。
小…P7928 [COCI2021-2022#1] Kamenčići
题目大意
小 A A A和小 B B B在玩游戏。在他们面前有 n n n块石头排成一行石头有红和蓝两种颜色。
小 A A A先手每次每人从两段中的一段取出一块石头谁先取出 k k k块石头谁就输。
小 A A A和小 B B B都采用最优策略问最后谁能获胜。
输入中 C C C表示红色石头 P P P表示蓝色石头。
如果小 A A A获胜则输出 D A DA DA否则输出 N E NE NE。 1 ≤ k ≤ n ≤ 350 1\leq k\leq n\leq 350 1≤k≤n≤350红色石头至少出现 2 k − 1 2k-1 2k−1次。 题解
可以看出这道题要用区间 D P DP DP。
设 f i , j , v f_{i,j,v} fi,j,v表示当前这段石头是原来 n n n个石头的第 i i i个到第 j j j个且小 B B B手中有 v v v块红色石头最后是否是小 A A A获胜。因为在确定左右边界的情况下被拿走的红色石头的数量是一定的所以小 A A A手中的红色石头可以由被拿走的红色石头减去小 B B B手中的红色石头得出是确定的不需要记录状态。
直接 D P DP DP好像不太方便我们考虑记忆化搜索。求 f i , j , v f_{i,j,v} fi,j,v的时候去搜索下一步的结果在以此来得出 f i , j , v f_{i,j,v} fi,j,v的值。当小 A A A或小 B B B手中的红色石头为 k k k时胜负就已经确定不需要再向下搜索了所以 v ≤ k v\leq k v≤k。
最多会搜索到 n 2 k n^2k n2k种状态所以时间复杂度为 O ( n 2 k ) O(n^2k) O(n2k)。
注意因为这题的空间为 128 M B 128MB 128MB所以直接开 35 0 3 350^3 3503的数组会 M L E MLE MLE。依题意 2 k − 1 ≤ n 2k-1\leq n 2k−1≤n即 k ≤ 175 k\leq 175 k≤175开 350 × 350 × 200 350\times 350\times 200 350×350×200的数组就可以了。
code
#includebits/stdc.h
using namespace std;
int n,k,f[355][355][205];
char s[355];
bool dfs(int l,int r,int v1,int v2,int fl){if(f[l][r][v2]!-1) return f[l][r][v2];if(v1k) return f[l][r][v2]0;if(v2k) return f[l][r][v2]1;if(fl1){if(lr) return f[l][r][v2]0;if(dfs(l1,r,v1(s[l]C),v2,2)||dfs(l,r-1,v1(s[r]C),v2,2)) return f[l][r][v2]1;else return f[l][r][v2]0;}else{if(lr) return f[l][r][v2]0;if(!dfs(l1,r,v1,v2(s[l]C),1)||!dfs(l,r-1,v1,v2(s[r]C),1)) return f[l][r][v2]0;else return f[l][r][v2]1;}
}
int main()
{scanf(%d%d,n,k);scanf(%s,s1);memset(f,-1,sizeof(f));if(dfs(1,n,0,0,1)) printf(DA);else printf(NE);return 0;
}
