硬币游戏
【题目描述】
小 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 }
百度公司福利 605人发布
投递百度等公司6个岗位 >
