【题解】跳格子2
【题目描述】
地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最小得分是多少。
【输入描述】
一行四个整数n,A,B,C(n≤100000,0≤A,B,C≤10000)，其中n表示格子的数量。x[i]由如下方式生成：
for (int i = 1; i <= n; i++){
int tmp = ((long long)A * i * i + B * i + C) % 20000;
x[i] = tmp - 10000;
}
【输出描述】
一行一个整数ans表示可能的最小得分。
【样例输入】
3 1 1 1
【样例输出】
-29977
【参考答案】
#include<bits/stdc++.h>
using namespace std;
int x[100010],n,A,B,C;
int main(){
cin>>n>>A>>B>>C;
for (int i = 1; i <= n; i++){
int tmp = ((long long)A * i * i + B * i + C) % 20000;
x[i] = tmp - 10000;
}
for (int i = 2; i <= n+1; i++){
x[i] = min(x[i-1],x[i-2]) + x[i];
}
cout<<x[n+1];
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。