小红书4.23笔试第一题 数组增值 AC

一开始用队列存发现内存占用过多,后来折腾了几轮发现居然可以dp,因为每个数字增加的操作次数都是固定的
下面这样可以AC
```cpp
const int MOD = 1e9 + 7;

int main()
{
int n;
cin >> n;
vector<int> arr;
int max = -1;
while (n--)
{
int a;
cin >> a;
arr.push_back(a);
if (a > max)
max = a;
}
// long long类型
vector<long long> dp(max + 1, 0);
vector<long long> mem(max + 1, 0);
dp[0] = 1;
dp[1] = 3;
mem[1] = dp[0];
for (int i = 2; i <= max; ++i)
{
// 这里也要mod 不mod只能A36%
dp[i] += (mem[i - 1] + i * dp[i - 1]) % MOD;
mem[i] = dp[i];
dp[i] += (i + 1) % MOD;
}

long long res = 0;
for (auto i : arr)
res = (res + dp[i]) % MOD;

cout << res;
}
```
全部评论
uu什么岗
点赞 回复 分享
发布于 2023-04-24 18:24 湖北
递归为什么只能过45啊
点赞 回复 分享
发布于 2023-04-23 18:05 广东

相关推荐

见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务