自动搬运

查看原文

来自洛谷，原作者为

	qwerty12346 这个家伙很懒，什么也没有留下(互关)

搬运于2025-08-24 22:01:00，当前版本为作者最后更新于2023-05-24 22:27:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

这题就是问那个团队会赢。

思路

直接动态规划来做这题，然后优化一下，再用一个前缀和，就能满分，如果不用前缀和这题只能拿 $70$ 分。我们的策略也很好判断，对于第 $i$ 只羊，如果后面 $k$ 只羊都不是自己的同类，那么此时我们的状态就只需要将败变胜，将胜变败就可以了。

状态定义

$dp_{i,j}$ 表示轮到第 $i$ 个人，还剩 $j$ 个石子时能否胜利。

边界考虑

要把 $dp_{i,0}$ 的初始值赋值为 $0$。但因为 $dp$ 数组是全局变量。初始值本来就是 $0$。所以可以不用循环赋值。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[5005][5005],b[10005],c[10005];
bool f[5005][5005];
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
	cin>>c[i];
	f[i][1]=!c[i];
	b[i]=(i+1)%n;
	a[i][1]=!c[i];
    }
    for(int i=2;i<=m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[b[j]][i-1]-a[b[j]][max(0,i-k-1)]==((!c[j])*min(i-1,k)))f[j][i]=!c[j];
	    else f[j][i]=c[j];
	    a[j][i]=a[j][i-1]+f[j][i];
	}
    }
    for(int i=0;i<n;i++)cout<<f[i][m]<<" ";
    return 0;
}