P4522 [COCI2017-2018#4] Vođe
qwerty12346
·
·
题解
题目传送门
题意
这题就是问那个团队会赢。
思路
直接动态规划来做这题，然后优化一下，再用一个前缀和，就能满分，如果不用前缀和这题只能拿 70 分。我们的策略也很好判断，对于第 i 只羊，如果后面 k 只羊都不是自己的同类，那么此时我们的状态就只需要将败变胜，将胜变败就可以了。
状态定义
## 边界考虑
要把 $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;
}
```