会HTML怎么做网站,北京软件研发公司,九江市网站建设,个人网站可以做导航[COCI2021-2022#1] Kamenčići 解题记录 题意简述
一个长度为 N N N 的字符串 S S S#xff0c;仅由 C 和 P 组成。轮流每次从两端取出一个字符#xff0c;先取出 K K K 个 C 的失败#xff0c;求先手必胜还是必败。 题目分析
考虑区间 DP#xff0c;设 d p l , r ,…[COCI2021-2022#1] Kamenčići 解题记录 题意简述
一个长度为 N N N 的字符串 S S S仅由 C 和 P 组成。轮流每次从两端取出一个字符先取出 K K K 个 C 的失败求先手必胜还是必败。 题目分析
考虑区间 DP设 d p l , r , k dp_{l,r,k} dpl,r,k 表示取到还剩区间 [ l , r ] [l,r] [l,r]当前轮到的人已经取了 k k k 个 C当前状态是必胜还是必败。 因为只剩一个石子的状态是确定的所以区间从少往多转移即区间 [ l , r ] [l,r] [l,r] 从区间 [ l 1 , r ] [l1,r] [l1,r] 和 [ l , r − 1 ] [l,r-1] [l,r−1] 转移。 下一个取得的数量 t t t 怎么求 假设我们取到了 [ l , r ] [l,r] [l,r]并且当前有 k k k 个 C 被取了那么 t t t 就是区间 [ l − 1 , r 1 ] [l-1,r1] [l−1,r1] 的 C 的数量减去现在的 k k k用前缀和维护。 由于相邻的两个状态相反所以转移的时候需要取反。 状态转移方程 d p l , r , k ¬ d p l 1 , r , t ∨ ¬ d p l , r − 1 , t dp_{l,r,k}\lnot \ dp_{l1,r,t} \vee \lnot \ dp_{l,r-1,t} dpl,r,k¬ dpl1,r,t∨¬ dpl,r−1,t AC Code
#includebits/stdc.h
#define arrout(a,n) rep(i,1,n)std::couta[i]
#define arrin(a,n) rep(i,1,n)std::cina[i]
#define rep(i,x,n) for(int ix;in;i)
#define dep(i,x,n) for(int ix;in;i--)
#define erg(i,x) for(int ihead[x];i;ie[i].nex)
#define dbg(x) std::cout#x:x
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a1,a1n
#define PII std::pairint,int
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N355;
int32_t n,K,dp[N][N][N/2],sum1[N],sum2[N];
std::string s;
int dfs(int l,int r,int k){if(dp[l][r][k]!-1){return dp[l][r][k];}if(kK){return 0;}int tsum1[l-1]sum2[r1]-k;if(tK){return 1;}int ans(!dfs(l1,r,t)|!dfs(l,r-1,t));return dp[l][r][k]ans;
}
signed main() {std::cinnKs;s s;mem(dp,-1);rep(i,1,n){sum1[i]sum1[i-1](s[i]C);}dep(i,n,1){sum2[i]sum2[i1](s[i]C);}if(dfs(1,n,0)){puts(DA);}else{puts(NE);}return 0;
}
