HDU - 5586 Sum——dp求最大连续和

HDU - 5586 Sum——dp求最大连续和

f(x)=(1890x+143)mod10007

题意：给你n个数，这n个数可以根据上面的规则进行变换，现在你要做的是选中一个区间（可以不选），把这个区间里的所有数按照规则变换，使得这n个数的和最大

思路：原数列为a，变换后的数列为b，用b-a就可以得到每一个数变化完之后对总和的贡献（可正可负），然后求数列b-a的最大连续和与a的总和相加即可

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, a[maxn], b[maxn], dp[maxn];int main() { while (scanf("%d", &n) == 1) { int sum = 0, ans = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = (1890 * a[i] + 143) % 10007 - a[i]; sum += a[i]; } dp[0] = 0; for (int i = 1; i <= n; i++) { if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + b[i]; else dp[i] = b[i]; ans = max(ans, dp[i]); } printf("%d\n", sum + ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。