1510: 【入门】跳格子2
内存限制：16 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：7
题目描述
地面上有一排长度为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 a[100100],dp[100100],n,i,ans;
int main(){
int A,B,C;
cin>>n>>A>>B>>C;
for (i = 1;i <=n ;i++) {
int tmp = ((long long)A * i * i + B * i + C) % 20000;
a[i] = tmp - 10000;
}
dp[1]=a[1];
dp[2]=min(a[2],a[1]+a[2]);
for (i = 3;i <= n;i++) {
dp[i]=min(dp[i-1],dp[i-2])+a[i];
}
ans=min(dp[n],dp[n-1]);
cout<<ans;
return 0;
}