【题目描述】

小 H 参加了一场神秘的游戏。游戏中有 n 堆硬币,第 i 堆价值 ai。每次小 H 可以选择编号相差 k 的硬币同时拿走。注意拿走后硬币不进行重标号。小 H 想知道最多能拿走多大价值的硬币。

【输入格式】

输入文件coin.in

第一行两个整数 n,k。

第二行 n 个整数。第 i 个整数表示 ai。

【输出格式】

输出文件coin.out

一行一个整数,表示拿走硬币的最大价值。

【样例输入】

7 3

7 5 8 6 4 3 2

【样例输出】

33

【数据范围】

对于 20%的数据,n<=20。

对于 40%的数据,n<=2000。

对于另外 20%的数据,k<=10。

 

认真理解题意可以发现，我么可以将每个硬币的编号模k，分成k组，同一组之间的硬币是会冲突的（既拿了一部分，就可能会有一部分不能拿），

不同组之间硬币是不会冲突的，这样问题就被简化了，我们再去考虑每一组，如果该组里面的硬币个数是偶数个，那么这一组的硬币都可以全部拿走

（好好理解），如果为奇数个的话，那么就会有一个无法拿走，在仔细分析，可以发现只可以将该组里第奇数个留下，（如果拿走第奇数个，那么前

面拿走的就会是奇数个，不符合题意），那么思路就明显了，具体参考代码就很容易明白了。

附上代码

 1 #include<Cstdio>
 2 #include<Iostream>
 3 using namespace std;
 4 int n,k,js[100010]; 
 5 long long sum[100010],a[100010],z;
 6 int main()
 7 {
 8     scanf("%d%d",&n,&k);
 9     for(int i=1;i<=n;++i)
10     {
11         scanf("%I64d",&a[i]);
12         z+=a[i];
13     }
14     for(int i=0;i<k;++i)
15     {
16         sum[i]=99999999999;
17     }
18     for(int i=1;i<=n;++i)
19     {
20         js[i%k]++;
21         if(a[i]<sum[i%k]&&js[i%k]%2==1)
22         {
23             sum[i%k]=a[i];
24         }
25     }
26     for(int i=0;i<k;++i)
27     {
28         if(js[i]%2==1)
29         z-=sum[i];
30     }
31     printf("%I64d",z);
32     return 0;
33 }