[JZOJ 5778] 초연 없는 전쟁.

1217 단어
사고방식:\(dp[i][j]=0/1\)를 외워서 제\(i\)개 동물보의 숫자가\(j\)이고 필승 전략이 있는지 없는지를 나타낸다.옮겼는지 안 옮겼는지 판단하면 돼.출력은 모든 동물에 대해\(dp[i][1->k]\)필승 전략이 있는지 확인하면 됩니다.
#include 
using namespace std;
int n,m,k;
int a[5010];
bool dp[5010][5010];
int suf[5010][5010];
int main () {
    freopen("vode.in","r",stdin);
    freopen("vode.out","w",stdout);
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1;i <= n; ++i) {
        scanf("%d",&a[i]);
    }
    for(int i = 1;i <= n; ++i) dp[i][m] = 0;
    for(int i = m - 1;i >= 1; --i) {
        for(int j = n;j >= 1; --j) {
            if(suf[j % n + 1][i + 1] - suf[j % n + 1][min(i + k,m) + 1]) dp[j][i] = 1;
            if(a[j] != a[j % n + 1]) dp[j][i] ^= 1;
            suf[j][i] = suf[j][i + 1] + dp[j][i];
        }
    }
    for(int i = 1;i <= n; ++i) {
        printf("%d ",(suf[i][1] - suf[i][k + 1]) ? a[i] : a[i] ^ 1);
    }
    return 0;
}
/*
Input 1
2 9 2
0 1
Input 2
6 499 5
1 0 0 1 1 0
Input 3
10 100 10
0 0 0 1 1 1 1 0 1 1

Output 1
0 1
Output 2
0 1 1 1 1 0
Output 3
1 1 1 1 1 1 1 1 1 1
*/

전재 대상:https://www.cnblogs.com/akoasm/p/9562598.html

좋은 웹페이지 즐겨찾기