大家好,又见面了,我是你们的朋友全栈君。
题意:给予n个房间,每个房间可以的到x个金币(x可能为负数),可以进行两种操作:
- 右移3i个房间,并且打开除最后一个的所有房间,如在1号房间,第一次移动可以移动到4号,并且打开1,2,3三个房间。
- 只右移3i个房间。
如果他走到最后一个房间,那么本轮游戏结束,求起点分别从1到n号房间开始最多能拿到多少金币,(金币数量不为负数)。
题意:i是第i次移动而不是第i个房间,这一点被坑到哭,一开始暴力将他这一次能打开的房间获得的金币数全部加起来,如果为正就执行操作一,否则执行操作二,虽然能过,但是耗时有点长。其实可以把这个房间前所有房间获得的金币数加起来,a[i]-a[i-1]就是这个房间能获得的金币数量,如果这一次从i移动到j那么a[j-1]-a[i-1]就是此次移动能获得的金币数量。
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
int main()
{
int a[500050],sum,i,j,k,q,n;
scanf("%d",&n);
a[0] = 0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i] += a[i-1];
}
for(i=1;i<=n;i++)
{
q = 3;
sum = 0;
for(j=i;j<=n;j+=q,q+=3)
{
k = j + q - 1;
//printf("\t%d\n",k);
if(k>n)
k = n;
sum += max(0,a[k] - a[j-1]);
}
printf("%d\n",sum);
}
return 0;
}
转载于:https://www.cnblogs.com/luoxiaoyi/p/9896084.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107216.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...